Polynomial time deterministic method for testing primality of numbers
First Claim
1. A method for generating prime numbers, the method comprising the steps of:
- a. generating a random number ‘
n’
;
b. checking if the random number ‘
n’
is an exact power of another positive integer;
if the random number ‘
n’
is an exact power of another positive integer, then;
c. declaring the random number ‘
n’
to be composite; and
if the random number ‘
n’
is not an exact power of another positive integer, then;
d. performing an extension ring test on the random number ‘
n’
.
1 Assignment
0 Petitions
Accused Products
Abstract
A method and a system for generating prime numbers and testing for primality of an integer. This invention has applicability to “public key” and other encryption techniques that play an important role in the security of information technology and electronic commerce. Generation of prime numbers requires the step of testing the primality. The method includes a deterministic test for testing the primality of a number in polynomial time. The system comprises a random number generator and a primality tester. The random number generator generates a random number and the primality tester tests the primality of this random number. The primality tester can also be used independent of the random number generator. In such a case, the number whose primality is to be tested can be input via a user interface.
-
Citations
21 Claims
-
1. A method for generating prime numbers, the method comprising the steps of:
-
a. generating a random number ‘
n’
;
b. checking if the random number ‘
n’
is an exact power of another positive integer;
if the random number ‘
n’
is an exact power of another positive integer, then;
c. declaring the random number ‘
n’
to be composite; and
if the random number ‘
n’
is not an exact power of another positive integer, then;
d. performing an extension ring test on the random number ‘
n’
. - View Dependent Claims (2, 3, 5)
-
-
4. A method for generating prime numbers, the method comprising the steps of:
-
a. generating a random number ‘
n’
;
b. checking if the random number ‘
n’
is an exact power of another positive integer;
if the random number ‘
n’
is an exact power of another positive integer, then;
c. declaring the random number ‘
n’
to be composite; and
if the random number ‘
n’
is not an exact power of another positive integer, then;
d. performing an extension ring test, the extension ring test comprising;
i. determining the smallest number ‘
r’
less than the random number ‘
n’
, the number ‘
r’
satisfying the following conditions;
1. the number ‘
r’
is a prime number;
2. the largest prime factor ‘
q’
of (r−
1) is greater than or equal to (4{square root}r log2 n);
3. n(r−
1)/q≠
1 mod (r); and
4. the greatest common divisor of the number ‘
r’ and
the random number ‘
n’
is equal to 1;
if no number ‘
r’
satisfying all the conditions specified in step a exists, then for all values of the number ‘
r’
less than the random number ‘
n’
;
ii. performing a check whether the greatest common divisor of the number ‘
r’ and
the random number ‘
n’
is greater than 1; and
if the greatest common divisor of ‘
r’ and
‘
n’
is greater than 1 for any value of the number ‘
r’
, then;
1. declaring the number ‘
n’
to be composite; and
if the greatest common divisor of ‘
r’ and
‘
n’
is equal to 1 for all values of the number ‘
r’
, then;
2. declaring the number ‘
n’
to be prime;
if a number ‘
r’
satisfying the conditions specified in step a exists, then;
iii. checking whether (x+a)n=xn+a mod (n, xr−
1) for all integer values of ‘
a’
from 1 to (2{square root}r log2 n);
if (x+a)n=xn+a mod (n, xr−
1) for any integer value of ‘
a’
between 1 and (2{square root}r log2 n), then;
1. declaring the number ‘
n’
to be composite; and
if (x+a)n=xn+a mod (n, xr−
1) for all integer values of ‘
a’
from 1 to (2{square root}r log2 n), then;
2. declaring the random number ‘
n’
to be prime. - View Dependent Claims (6)
-
-
7. A method of deterministically testing primality of a random number ‘
- n’
in polynomial time, the method comprising the steps of;
a. checking if the random number ‘
n’
is an exact power of another positive integer;
if the random number ‘
n’
is an exact power of another positive integer, then;
b. declaring the random number ‘
n’
to be composite; and
if the random number ‘
n’
is not an exact power of another positive integer, then;
c. performing an extension ring test. - View Dependent Claims (8, 9, 11)
- n’
-
10. A method of deterministically testing primality of a random number ‘
- n’
in polynomial time, the method comprising the steps of;
a. checking if the random number ‘
n’
is an exact power of another positive integer;
if the random number ‘
n’
is an exact power of another positive integer, then;
b. declaring the random number ‘
n’
to be composite;
if the random number ‘
n’
is not an exact power of another positive integer, then;
c. performing an extension ring test, the extension ring test comprising;
i. determining the smallest number ‘
r’
less than the random number ‘
n’
, the number ‘
r’
satisfying the following conditions;
1. the number ‘
r’
is a prime number;
2. the largest prime factor ‘
q’
of (r−
1) is greater than or equal to (4{square root}r log2 n);
3. n(r−
1)/q≠
1 mod (r); and
4. the greatest common divisor of the number ‘
r’ and
the random number ‘
n’
is equal to 1;
if no number ‘
r’
satisfying all the conditions specified in step a exists, then for all values of the number ‘
r’
less than the random number ‘
n’
;
ii. performing a check whether the greatest common divisor of the number ‘
r’ and
the random number ‘
n’
is greater than 1; and
if the greatest common divisor of ‘
r’ and
‘
n’
is greater than 1 for any value of the number ‘
r’
, then;
1. declaring the number ‘
n’
to be composite; and
if the greatest common divisor of ‘
r’ and
‘
n’
is equal to 1 for all values of the number ‘
r’
, then;
2. declaring the number ‘
n’
to be prime;
if a number ‘
r’
satisfying the conditions specified in step a exists, then;
iii. checking whether (x+a)n=xn+a mod (n, xr−
1) for all integer values of ‘
a’
from 1 to (2{square root}r log2 n);
if (x+a)n≠
xn+a mod (n, xr−
1) for any integer value of ‘
a’
between 1 and (2{square root}r log2 n), then;
1. declaring the number ‘
n’
to be composite; and
if (x+a)n=xn+a mod (n, xr−
1) for all integer values of ‘
a’
from 1 to (2{square root}r log2 n), then;
2. declaring the random number ‘
n’
to be prime. - View Dependent Claims (12)
- n’
-
13. A system for deterministically testing primality of a random number ‘
- n’
in polynomial time, the system comprising;
a. means for checking if the random number ‘
n’
is an exact power of another positive integer;
if the random number ‘
n’
is an exact power of another positive integer, then;
b. means for declaring the random number ‘
n’
to be composite; and
if the random number ‘
n’
is not an exact power of another positive integer, and;
c. means for performing an extension ring test. - View Dependent Claims (14, 15)
- n’
-
16. A system for encrypting a communication, said system including a prime number generator, wherein the improvement comprises:
- the prime number generator having a random number generator for generating a random number ‘
n’ and
;
means for checking if the random number ‘
n’
is an exact power of another positive integer;
if the random number ‘
n’
is an exact power of another positive integer, then declaring the random number ‘
n’
to be composite;
if the random number ‘
n’
is not an exact power of another positive integer, then performing an extension ring test on the random number ‘
n’
so as to determine whether the random number is prime. - View Dependent Claims (17, 18)
- the prime number generator having a random number generator for generating a random number ‘
-
19. A system for encrypting a communication, said system including a prime number generator, wherein the improvement comprises:
a. the prime number generator including;
i. a random number generator for generating a random number ‘
n’ and
;
ii. means for checking if the random number ‘
n’
is an exact power of another positive integer;
iii. means for declaring the random number ‘
n’
to be composite;
iv. means for performing an extension ring test on the random number ‘
n’
; and
v. means for declaring the random number ‘
n’
to be prime.- View Dependent Claims (20, 21)
Specification