Changeset 1a3911 in git for Singular/LIB/crypto.lib
- Timestamp:
- Apr 6, 2009, 2:39:02 PM (15 years ago)
- Branches:
- (u'spielwiese', '5b153614cbc72bfa198d75b1e9e33dab2645d9fe')
- Children:
- 08e081516771eec845058a046616a8c0d7e8325b
- Parents:
- 7de8e4cf4e88e60e523f5ebb65a61c114ff3674a
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
Singular/LIB/crypto.lib
r7de8e4 r1a3911 1 1 //GP, last modified 28.6.06 2 2 /////////////////////////////////////////////////////////////////////////////// 3 version="$Id: crypto.lib,v 1. 6 2008-10-09 09:31:57 SingularExp $";3 version="$Id: crypto.lib,v 1.7 2009-04-06 12:39:02 seelisch Exp $"; 4 4 category="Teaching"; 5 5 info=" … … 8 8 9 9 NOTE: The library contains procedures to compute the discrete logarithm, 10 primal y-tests, factorization included elliptic curve methodes.10 primality-tests, factorization included elliptic curves. 11 11 The library is intended to be used for teaching purposes but not 12 12 for serious computations. Sufficiently high printlevel allows to … … 65 65 proc decimal(string s) 66 66 "USAGE: decimal(s); s = string 67 RETURN: the (decimal) number corresponding to the hexadecimal number s67 RETURN: the (decimal) number corresponding to the hexadecimal number s 68 68 EXAMPLE:example decimal; shows an example 69 69 " … … 103 103 proc exgcdN(number a, number n) 104 104 "USAGE: exgcdN(a,n); 105 RETURN: a list s,t,d of numbers ,d=gcd(a,n)=s*a+t*n105 RETURN: a list s,t,d of numbers satisfying d=gcd(a,n)=s*a+t*n 106 106 EXAMPLE:example exgcdN; shows an example 107 107 " … … 510 510 "USAGE: babyGiant(b,y,p); 511 511 RETURN: the discrete logarithm x: b^x=y mod p 512 NOTE: giant-step-baby-step512 NOTE: This procedure works based on Shank's baby step - giant step method. 513 513 EXAMPLE:example babyGiant; shows an example 514 514 " … … 561 561 NOTE: Pollard's rho: 562 562 choose random f_0 in 0,...,p-2 ,e_0=0, define x_0=b^f_0, define 563 x_i=y^e_i b^f_i as below. For i large enough there is i with563 x_i=y^e_i*b^f_i as below. For i large enough there is i with 564 564 x_(i/2)=x_i. Let s:=e_(i/2)-e_i mod p-1 and t:=f_i-f_(i/2) mod p-1, 565 565 d=gcd(s,p-1)=u*s+v*(p-1) then x=tu/d +j*(p-1)/d for some j (to be … … 649 649 RETURN: 1 if n is prime, 0 else 650 650 NOTE: probabilistic test of Miller-Rabin with k loops to test if n is prime. 651 Using the theorem: If n is prime, n-1=2^s*r, r odd, then651 Using the theorem: If n is prime, n-1=2^s*r, r odd, then 652 652 powerN(a,r,n)=1 or powerN(a,r*2^i,n)=-1 for some i 653 653 EXAMPLE:example MillerRabin; shows an example … … 701 701 RETURN: 1 if n is prime, 0 else 702 702 NOTE: probabilistic test of Soloway-Strassen with k loops to test if n is 703 prime using the theorem: 704 If n is prime thenpowerN(a,(n-1)/2,n)=Jacobi(a,n) mod n703 prime using the theorem: If n is prime then 704 powerN(a,(n-1)/2,n)=Jacobi(a,n) mod n 705 705 EXAMPLE:example SolowayStrassen; shows an example 706 706 " … … 746 746 L a list of the first k primes 747 747 RETURN:message N is not prime or {A,{p},{a_p}} as certificate for N being prime 748 NOTE:assumes that it is possible to factorize N-1=A*B such that gcd(A,B)=1 748 NOTE:assumes that it is possible to factorize N-1=A*B such that gcd(A,B)=1, 749 749 the factorization of A is completely known and A^2>N . 750 750 N is prime if and only if for each prime factor p of A we can find … … 830 830 "USAGE: PollardRho(n,k,allFactors); optional: PollardRho(n,k,allFactors,L); 831 831 L a list of the first k primes 832 RETURN: a list of factors of n (which could be just n),if allFactors=0 832 RETURN: a list of factors of n (which could be just n),if allFactors=0@* 833 833 a list of all factors of n ,if allFactors=1 834 834 NOTE: probabilistic rho-algorithm of Pollard to find a factor of n in k loops. … … 933 933 NOTE: Pollard's p-factorization 934 934 creates the product k of powers of primes (bounded by B) from 935 the list P with the idea that for a prime divisor p of n p-1|k936 then p devides gcd(a^k-1,n) for some random a935 the list P with the idea that for a prime divisor p of n we have 936 p-1|k, and then p devides gcd(a^k-1,n) for some random a 937 937 EXAMPLE:example pFactor; shows an example 938 938 " … … 974 974 k for using the first k elements in B 975 975 RETURN: a list of factors of n or the message: no divisor found 976 NOTE: quadraticSieve: Ideais to find x,y such that x^2=y^2 mod n then976 NOTE: The idea being used is to find x,y such that x^2=y^2 mod n then 977 977 gcd(x-y,n) can be a proper divisor of n 978 978 EXAMPLE:example quadraticSieve; shows an example … … 1128 1128 "USAGE: ellipticAdd(N,a,b,P,Q); 1129 1129 RETURN: list L, representing the point P+Q 1130 NOTE: P=(P[1]:P[2]:P[3]), Q =(Q[1]:Q[2]:Q[3])points on the elliptic curve1130 NOTE: P=(P[1]:P[2]:P[3]), Q=(Q[1]:Q[2]:Q[3]) points on the elliptic curve 1131 1131 defined by y^2z=x^3+a*xz^2+b*z^3 over Z/N 1132 1132 EXAMPLE:example ellipticAdd; shows an example … … 1350 1350 RETURN: the number of points of the elliptic curve defined by 1351 1351 y^2=x^3+a*x+b over Z/N 1352 NOTE: trivial ap roach1352 NOTE: trivial approach 1353 1353 EXAMPLE:example countPoints; shows an example 1354 1354 " … … 1420 1420 1421 1421 proc ShanksMestre(number q, number a, number b, list #) 1422 "USAGE: ShanksMestre(q,a,b); optional: ShanksMestre(q,a,b,s); s the number1422 "USAGE: ShanksMestre(q,a,b); optional: ShanksMestre(q,a,b,s); s the number 1423 1423 of loops in the algorithm (default s=1) 1424 1424 RETURN: the number of points of the elliptic curve defined by 1425 1425 y^2=x^3+a*x+b over Z/N 1426 NOTE: algorithm of Shanks and Mestre ( giant-step-baby-step)1426 NOTE: algorithm of Shanks and Mestre (baby-step-giant-step) 1427 1427 EXAMPLE:example ShanksMestre; shows an example 1428 1428 " … … 1575 1575 "USAGE: generateG(a,b,m); 1576 1576 RETURN: m-th division polynomial 1577 NOTE: generate the recursively defined polynomials in Z[x,y],so called1578 division polynomials, p_m=generateG(a,b,m) such that on the elliptic curve1579 defined by y^2=x^3+a*x+b over Z/N and a point P=(x:y:1) the point m*P is 1580 1581 m*P=0 iff p_m(P)=01577 NOTE: generate the so-called division polynomials, i.e., the recursively defined 1578 polynomials p_m=generateG(a,b,m) in Z[x, y] such that, for a point (x:y:1) on the 1579 elliptic curve defined by y^2=x^3+a*x+b over Z/N the point@* 1580 m*P=(x-(p_(m-1)*p_(m+1))/p_m^2 :(p_(m+2)*p_(m-1)^2-p_(m-2)*p_(m+1)^2)/4y*p_m^3 :1) 1581 and m*P=0 iff p_m(P)=0 1582 1582 EXAMPLE:example generateG; shows an example 1583 1583 " … … 1846 1846 d+1 the number of loops in the algorithm (default d=0) 1847 1847 RETURN: a factor of N or the message no factor found 1848 NOTE: - computes a factor of N using Lenstra's ECM factorization 1848 NOTE: - computes a factor of N using Lenstra's ECM factorization@* 1849 1849 - the idea is that the fact that N is not prime is dedected using 1850 1850 the operations on the elliptic curve … … 1901 1901 proc ECPP(number N) 1902 1902 "USAGE: ECPP(N); 1903 RETURN: message:N is not prime or {L,P,m,q} as certificate for N being prime 1904 L a list (y^2=x^3+L[1]*x+L[2] defines an elliptic curve C) 1905 P a list ((P[1]:P[2]:P[3]) is a point of C) 1903 RETURN: message:N is not prime or {L,P,m,q} as certificate for N being prime@* 1904 L a list (y^2=x^3+L[1]*x+L[2] defines an elliptic curve C)@* 1905 P a list ((P[1]:P[2]:P[3]) is a point of C)@* 1906 1906 m,q integers 1907 1907 ASSUME: gcd(N,6)=1
Note: See TracChangeset
for help on using the changeset viewer.