Prev: Riemann-Siegel Z function and Lehmer's phenomenon
Next: 【 P = NP Quod Erat Demonstrandum 】の検索結果
From: Future_News on 21 Oct 2009 13:08
On Oct 21, 4:42 am, Nick Keighley <nick_keighley_nos...(a)hotmail.com>
wrote:
> On 21 Oct, 12:16, "Dik T. Winter" <Dik.Win...(a)cwi.nl> wrote:
>
> > In article <8cd1164c-9d0f-4dc5-ae93-13f2bfeb8...(a)d23g2000vbm.googlegroups.com> Nick Keighley <nick_keighley_nos...(a)hotmail.com> writes:
> >  > On 21 Oct, 08:03, "http://alexslemonade.org(a)http://MeAmI.org" > <marty.musa...(a)gmail.com> wrote:
>
> > ...
> >  > don't post the same stuff over and over again.
> >  > don't post Fortran to comp.lang.c.
>
> > Don't reply to Marty Musatov who has already succeeded in making sci.math
> > unreadable.
>
> ah, I hadn't recognised him

inget{ the name is Mart:in-out+

???? ? ??
????



0942777 ???
0942782 ???
0942784 ???
0942806 ???



Prime number and generator:
(a) Describe how to determine whether a given number is prime (see
pages 242-245 in the textbook). Note that you should find more
solutions for this problem and compare the performance between these
solutions.
(b) Describe how to determine whether a given number is a generator
of
Zp, where p is a prime number (please give an efficient algorithm).
Note
that the order of the generator you find is p -1.

(A)
??: ? p , p > 1 ? p ??????? p ? 1 ?? p ????? (prime number).
???: ???????1??????????????????? (composite number).
????a???????p????? ?gcd(a , p)=1?
?? : (Euclid) ?? p ?????,? a, b . ? p | ab, ? p | a ? p | b.
Proof: ??????? p | a ? p | b. ?? p | a ?????? (?????? p | b); ?? p a,
???????? p | b. ????? p a ?? gcd(p, a) = 1, ?p | b.

Proposition 1: ? n > 1 ????????????ûn??? p ????? n, ? n ????.
Proof:. ?????????? n ????, ???????. ?? n ????, ?????? a,
b ?? 1 < a?b < n ? n = ab. ???????? a?ûn, ??? a >ûn??? ab >
(ûn)2 = n ?? n = ab ??


????? : ???????????????????????????????????????
?????????????

??????????(Deterministic Primality Test)
?????????????????????????Guaranteed Prime??
1. ??? : ?????????????2??i?n-1???n??i???
??????n???i???????
bool isPrime(n) :
for (i = 2; i < n; i++)
if (n % i == 0)
return false;
return true;
2. ???????????????Proposition 1???????srqt(n)????
bool isPrime(n) :
for (i = 2; i * i <= n; i ++) //??srqt(n)
if (n % i == 0)
return false;
return true;
3. Erotosthenes? Sieve?
?. Write a list of numbers from 2 to the largest number you want to
test for primality.
Call this List A.
?. Write the number 2, the first prime number, in another list for
primes found. Call
this List B.
?. Strike off 2 and all multiples of 2 from List A.
?. The first remaining number in the list is a prime number. Write
this number into
List B.
?. Strike off this number and all multiples of this number from List
A. The
crossing-off of multiples can be started at the square of the number,
as lower
multiples have already been crossed out in previous steps.
?. Repeat steps 4 and 5 until no more numbers are left in List A.
????
// assume all numbers are prime at
first

is_prime(i) ? true, i ? [ 2, limit ]

for n in [ 2, ûlimit ] :
if is_prime( n ):
// eliminate multiples of each prime,
// starting with its square
is_prime(i) ? false, i ? { ný, ný+n, ný+2n, ..., limit }

for n in [ 2, limit ]:
if is_prime( n ) : print n

?????:
limit = 1000000
sieve$ = string of the character "P" with length limit

prime = 2
repeat while prime2 < limit
set the character at the index of each multiple of prime
(excluding index
prime * 1) in sieve$ to "N"
prime = index of the next instance of "P" in sieve$ after index
prime
end repeat

print the index of each instance of "P" in sieve$

??????? : ???2???
fill sieve[] with true;
for (int i=3; i < sqrt_MAX; i+=2)
if (sieve[i])
for (int j=i*i; j < MAX; j+=i*2)
sieve[j] = false;
??2??????????????????????????0?????1??1?????3?
?2?????5?????????

? ??????
??>3?????????????or ????????????
??????6n+1?6n+5????????2???3???????1~6??2?3?4??2?3
?????????????????6n+1?6n+5??????5???????????30n+1
30n+7 30n+11.....???????2 3 5????
??????
???
???? jump[] = { 6, 4, 2, 4, 2, 4, 6, 2 }
????? 1 ?????
1, 7, 11, 13, 17, 19, 23, 29,
31,37, 41, 43, 47, 49 <- ???????????

??????????(Probabilistic Primality Test)
??????????????????????Pseudo-Primes?????
?Pseudo-Primes?

Fermat?s theorem : ?p?????????p??????a?ap-1ð1 (mod p)
????n????????????????????a???an-1ð1 (mod n)???????n
???a????(base-a pseudoprime)??????????????????????????
(Fermat testing)????????????? ???????????
1. ????:
Test(n)
for i = 1 to t do
????a, 1 < a < n-1;
??r = an-1 (mod n)
if r ? 1 then output ????
output ???? ???????
?????????t???a???????????????????????????n?
??????n????a?an-1ð1 (mod n)?????n??????(Carmichael numbers)??
???n????a??????n??????????????????????????255?8
??????????????????561, 1105, 1729??????????n??????n?
?????????{ 2, ?, n-1}???n???????n=12?????n?????{ 5, 7, 11}?
?????????????????????a?{ 5, 7, 11}????{ 2, ?, 11}?
2. ??-???? :
???????????????????????????2?????????????????
?? q ?????????????t???? a ?????????????????????-
?????????????????a ????????????????????(1/4)a?t??
????????????
Two property of prime numbers:
First : ??p??????????p?????then a2 mod p = 1 if
and
only if a mod p = 1 ? a mod p = -1 mod p = p ? 1?????????
(a
mod p)(a mod p) = a2 mod p?a mod p = 1 ?a mod p = -1?then a2
mod p =1
?????a2 mod p =1?then (a mod p)2 = 1???if a mod p = 1 ?a mod
p = -1
Second : ?p??2??????p ? 1????2kq?k > 0?q odd?a??1<a<p-1
????????????2?????????
1. aq mod p = 1 ???aq ð 1 (mod) p
2. aq, a2q, a4q,?. a(2^k-1)q ?????? -1 mod p?????????1?j?k?j?
a(2^j-1)q mod p = -1 mod p = p ? 1?a(2^j-1)q ð -1 mod p
Proof: ???????an-1ð1 (mod n) if n is prime?we have p ? 1 = 2kq ,p is
prime?We look at the sequence of numbers:
a q mod p, a2q mod p, a4q mod p,?. a(2^k-1)q mod p, a(2^k)q mod p
????a(2^k)q mod p = 1???????????????????????????????
1. the first number on the list?and therefore all subsequent numbers
on the list
equals 1
2. some number on the list does not equal 1?but its square mod p does
equal 1?
By virtue of the first property?we know that the only number satisfies
this
condition is p ? 1. So, in this case, the list contains an element
equal to p ? 1?
Test(n)
Find integer k, q, with k > 0, q odd, so that (n - 1=2^k q);
????a, 1 < a < n-1;
If a^q mod n = 1 then return ( ?inconclusive? );
For j = 0 to k ? 1 do
If a^2jq mod n ð n ? 1 then return (?inconclusive?);
return (?composite?);
Definition of Zn: the set of nonnegative integersless than n
Zn = {0, 1, ???.., (n-1)}
???????
?? p ??????2^p?1?????????????? p=3?7??p=5?31??p=7?127?
?????????p=11?2047=23*89????????????????????????
?????????????????????????????2^p-1 ????????????
???


??????????????????????
AKS ????????

2002 ?????????Agrawal?Kayal?Saxena ????AKS ????AKS ???
??????????????(Finite Field)???????????????????a ?r ?
?n ??????????????????????????????????????????
?
????????
Input: Integer n > 1
if (n is has the form ab with b > 1) then output
COMPOSITE
r := 2
while (r < n)
{
if (gcd(n,r) is not 1) then output
COMPOSITE
if (r is prime greater than 2) then
{ let q be the largest factor of r-1
if (q > 4sqrt(r)log n) and (n(r-1)/q is not 1 (mod r))
then break
}
r := r+1
}
for a = 1 to 2sqrt(r)log n
{
if ( (x-a)n is not (xn-a) (mod xr-1,n) ) then
output COMPOSITE
}
output PRIME


Pollard?s Rho?

??????????????????????1975 ??John Pollard ??????????
???????????????????????Floyd's cycle-finding ?????????
?????????x and y ??mod p???p?n ???????1 < gcd(| x ? y |, n) œ n ?
??? n ????????f(x)????????mod n??? n ???????????????
1. x = 2, y = 2; d = 1
2. While d = 1:
A. x _ f(x)
B. y _ f(f(y))
C. d _ GCD(|x ? y|, n)
D. If 1 < d < n, then return d.
E. If d = n, return failure.


NFS?

??????????NFS?Number FieldSieve??????????100 ????????
???????Quadratic Polynomial??????????????????????????
x3+k ????????????1990 ????SNFS?Special Number Field Sieve???
?????????Fermat Number r s e ñ ?r?e?s?Z ??e > 0????????????
??????155 digits ????????????????????????GNFS?General
Number Field Sieve?????GNFS ??????????????GNFS ???????
???????? [12]
A. Selecting Polynomial
B. The Relational Factor Base
C. The Algebraic Factor Base
D. The Quadratic Character Base
E. Sieving
F. Forming the Matrix
G. Finding Dependencies
H. Computing the Explicit Square Root in Z[?]
I. Determining Applicable Finite Field
J. Square Root in Finite Field
K. Using the CRT????????
L. Putting it Together

(B)
?????? p ???????? modulo p ?????? primitive root.??????,
?????????: ??????????????????; ???????????????
????????? (?????????????????). ????????????????
???????????????????????. ???????????????????,
????? congruence equation ??????, ?????????????????.
???, ??? primitive root ??????, ??????????????????????
????? primitive root, ????????????????????.

Definition of Zn: the set of nonnegative integersless than n
Zn = {0, 1, ???.., (n-1)}
This is reffered to as the set of residues,or residue classes modulo n
Generator of Z*p: ? n ? p ????n order ð 1 (mod p) ???order????? p-1?
?n ???? p ?generator? ??n?1? p-1?? mod p?????Z*p?
permutation ??????????????

? Trivial algorithm
? Compute gi for all i (By repeated squaring)
? Search table for a
? Time complexity O(p)
? Shanks? algorithm (1972)
? Compute S = {(i, agi), i = 0, 1, ?, m)
T = {(i, gmi), i = 0, 1, ?, m)
where m = [(p-1) 1/2]
Sort S and T
? Find the same value from S and T, get agr = gmq so a = gmq - r
? Time complexity O(mlogm) = O(p 1/2 logp)
? Space complexity O(p 1/2)
example
G = Z*19 = { 1, 2, ?, 18}
g = 2, p = 19, m = 5 and assume a = 15
S: (0, 15) T: (0, 1)
(1, 11) (1, 13) r = 4
(2, 3) (2, 17) q = 3
(3, 6) (3, 12) mq - r = 11
(4, 12) (4, 4)
(5, 5) (5, 14)
? Pollard?s algorithm (1978)
compute integers s and t such that
? partition the group G into three roughly equal-sized set
S1 , S2 and S3 . Let x0=1G
?






where n = p-1 when G = Z*p
We should expect some integer such that
, then this gives with

If , then compute u such that
and we have , so that
If ,
little work to do...
? Pohlig-Hellman algorithm (1978)
? Suitable for q-1 has only small prime divisors
Assume c = am
? Base case : q-1 = 2n
? Let
because aq-1 = 1
hence


So we can compute m
?????
http://crypto.nknu.edu.tw/publications/2006Open_factor.pdf
http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
http://www.ice.ntnu.edu.tw/~u91029/number_theory.html










First  |  Prev  | 
Pages: 1 2
Prev: Riemann-Siegel Z function and Lehmer's phenomenon
Next: 【 P = NP Quod Erat Demonstrandum 】の検索結果