Class Prime

xiaoxiao2021-03-06 41

Import java.util.vector;

/ **

* This Class Implements The Lucas Prime Number Test.

* Lucas Test:

* A Number P> 1 IS Prime, IF a Number R EXISTS, WITH 1

* 1) R ^ (p-1) MOD P = 1

* 2) for All Prime Factors Q of P-1 IS: R ^ ((P-1) / Q) MOD P <> 1.

* are Met.

* @Author Holger Schmid

* @version 07.01.2000

* /

Class Prime

{

INT P; // Number to Test

Boolean isprime = false; // test result

Vector rlist = new vector (); // list of all r, what meet condition 1)

Vector Qlist = New Vector (); // Prime Factors Of P-1

/ ** CONSTRUCTS A NEW Number and test if it's prime.


* @Param Number the Number to Test
* /
Public Prime (int Number)
{
P = Number;
Lucasfindr ();
PFZ ();
Lucastestfast ();
Return;
}
/ ** Returns if this number is prime.
* @Return Result of Prime Test
* /
Public boolean isprime ()
{
Return isprime;
}
/ ** RETURNS All Prime Factors of P-1
* @Return List of Prime Factors
* /
Public Vector getqlist ()
{
Return Qlist;
}
/ ** RETURNS All R, That Meet Condition 1)
* @Return List of r
* /
Public Vector getRlist ()
{
Return rlist;
}
/ ** EXECUTES A FULL LUCAS TEST.
* @Return List of results for Output Purpose (ONE List of All Q for Each R)
* /
Public Vector LucasComplete ()
{
Vector result = new vector ();
INT I, J, Q, R;
Q = 0;
For (i = 0; i 
{// Test All R
Result.addeElement (New Vector ());
R = (Integer) rlist.ementatat (i)). INTVALUE ();
For (j = 0; j 
{// and all q
Q = ((Integer) QList.Elementat (j)). INTVALUE ();
IF (FORMEL (r, (p-1) / q, p) == 1)
{// condition 2) is not met (") result.lastelement ()). AddElement (" - ");
}
Else
{// condition 2) is Met
(Vector) Result.lastelement ()). AddElement (" ");
}
}
}
Return Result;
}
/ ** FINDS All R That Meet Condition 1)
* @return List of r, That Meet Condition 1)
* /
Public Vector Lucasfindr ()
{
Int r;
FOR (r = 2; r 
{// Test All Possible R with 1 
IF (Bedingung1 (R))
{
Rlist.addelement (New Integer (R));
}
}
Return rlist;
}
/ *** Compute All Prime Factors Q of P-1
* @Return List of Prime Factors
* /
Public Vector PFZ ()
{
QList = PFZ (P-1);
Return Qlist;
}
/ ** Executes A Fast Lucas Test. Only The Result P IS (Not) Prime is store.
* /
Private void lucastestfast ()
{
Int r;
FOR (r = 2; r 
{// Test All Possible R with 1 
IF (Bedingung1 (R))
{// check condition 2) Only if Condition 1) is Met
Bedingung2 (R))
{// p is prime
Isprime = true;
Return;
}
}
Else
{// Abort Test, Because Condition One IS Not Met
Return;
}
}
Return;
}
/ ** Check condition 1)
* @Return True if condition is Met
* /
Private Boolean Bedingung1 (Int R)
{
IF (FORMEL (R, P-1, P) == 1)
Return True;
Else
Return False;
}
/ ** Check Condition 2)
* @Return True if condition is Met
* /
Private Boolean Bedingung2 (INT R)
{
INT I, Q = 0;
For (i = 0; i 
{// Test Condition 2) for ALL Q
IF (q! = ((Integer) QList.Elementat (i)). INTVALUE ())
{// Test Only if new Prime Factor
q = ((Integer) QList.Elementat (i)). INTVALUE ();
IF (FORMEL (r, (p-1) / q, p) == 1)
Return False;
}
}
Return True;
}
/ *** Compute All Prime Factors of  x 

* @Return List of prime factory * /
Private Vector PFZ (INT X)
{
INT Q;
Vector pfTemp = new vector (10);
For (q = 2; q * q <= x; q   )
{// Test All Possible Factors
IF (x% q == 0)
{// q IS Prime Factor of X
Pftemp.addelement (new integer (q));
// ELIMINATE THIS FACTOR
x / = q;
Q -;
}
}
Pftemp.addelement (new integer (x));
Return PfTemp;
}
/ *** Compute  (a ^ b)% P 

* @Param a Value for Formula
* @Param B Value for Formula
* @Param P Value for Formula
* /
Int FORMEL (int A, int B, int C)
{
INT K, Bitmask, D, I;
K = 30; bitmask = 0x40000000;
D = 1;
For (i = k; i> = 0; i -)
{
D = (D * D)% C;
IF (B & Bitmask)> 0)
{
D = (D * a)% C;
}
Bitmask / = 2;
}
Return (D);
}
}


转载请注明原文地址:https://www.9cbs.com/read-60631.html

9cbs

New Post(0)