Changeset 1a3911 in git for Singular/LIB/crypto.lib


Ignore:
Timestamp:
Apr 6, 2009, 2:39:02 PM (15 years ago)
Author:
Frank Seelisch <seelisch@…>
Branches:
(u'spielwiese', '5b153614cbc72bfa198d75b1e9e33dab2645d9fe')
Children:
08e081516771eec845058a046616a8c0d7e8325b
Parents:
7de8e4cf4e88e60e523f5ebb65a61c114ff3674a
Message:
removed some docu errors prior to release 3-1-0


git-svn-id: file:///usr/local/Singular/svn/trunk@11626 2c84dea3-7e68-4137-9b89-c4e89433aadc
File:
1 edited

Legend:

Unmodified
Added
Removed
  • Singular/LIB/crypto.lib

    r7de8e4 r1a3911  
    11//GP, last modified 28.6.06
    22///////////////////////////////////////////////////////////////////////////////
    3 version="$Id: crypto.lib,v 1.6 2008-10-09 09:31:57 Singular Exp $";
     3version="$Id: crypto.lib,v 1.7 2009-04-06 12:39:02 seelisch Exp $";
    44category="Teaching";
    55info="
     
    88
    99NOTE: The library contains procedures to compute the discrete logarithm,
    10       primaly-tests, factorization included elliptic curve methodes.
     10      primality-tests, factorization included elliptic curves.
    1111      The library is intended to be used for teaching purposes but not
    1212      for serious computations. Sufficiently high printlevel allows to
     
    6565proc decimal(string s)
    6666"USAGE:  decimal(s); s = string
    67 RETURN: the (decimal)number corresponding to the hexadecimal number s
     67RETURN: the (decimal) number corresponding to the hexadecimal number s
    6868EXAMPLE:example decimal; shows an example
    6969"
     
    103103proc exgcdN(number a, number n)
    104104"USAGE:  exgcdN(a,n);
    105 RETURN: a list s,t,d of numbers, d=gcd(a,n)=s*a+t*n
     105RETURN: a list s,t,d of numbers satisfying d=gcd(a,n)=s*a+t*n
    106106EXAMPLE:example exgcdN; shows an example
    107107"
     
    510510"USAGE:  babyGiant(b,y,p);
    511511RETURN: the discrete logarithm x: b^x=y mod p
    512 NOTE:   giant-step-baby-step
     512NOTE:   This procedure works based on Shank's baby step - giant step method.
    513513EXAMPLE:example babyGiant; shows an example
    514514"
     
    561561NOTE: Pollard's rho:
    562562       choose random f_0 in 0,...,p-2 ,e_0=0, define x_0=b^f_0, define
    563        x_i=y^e_ib^f_i as below. For i large enough there is i with
     563       x_i=y^e_i*b^f_i as below. For i large enough there is i with
    564564       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,
    565565       d=gcd(s,p-1)=u*s+v*(p-1) then x=tu/d +j*(p-1)/d for some j (to be
     
    649649RETURN: 1 if n is prime, 0 else
    650650NOTE: 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, then
     651       Using the theorem: If n is prime, n-1=2^s*r, r odd, then
    652652       powerN(a,r,n)=1 or powerN(a,r*2^i,n)=-1 for some i
    653653EXAMPLE:example MillerRabin; shows an example
     
    701701RETURN: 1 if n is prime, 0 else
    702702NOTE: probabilistic test of Soloway-Strassen with k loops to test if n is
    703        prime using the theorem:
    704        If n is prime then powerN(a,(n-1)/2,n)=Jacobi(a,n) mod n
     703       prime using the theorem: If n is prime then
     704       powerN(a,(n-1)/2,n)=Jacobi(a,n) mod n
    705705EXAMPLE:example SolowayStrassen; shows an example
    706706"
     
    746746        L a list of the first k primes
    747747RETURN: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
     748NOTE:assumes that it is possible to factorize N-1=A*B such that gcd(A,B)=1,
    749749      the factorization of A is completely known and A^2>N .
    750750      N is prime if and only if for each prime factor p of A we can find
     
    830830"USAGE:  PollardRho(n,k,allFactors); optional: PollardRho(n,k,allFactors,L);
    831831         L a list of the first k primes
    832 RETURN: a list of factors of n (which could be just n),if allFactors=0
     832RETURN: a list of factors of n (which could be just n),if allFactors=0@*
    833833        a list of all factors of n ,if allFactors=1
    834834NOTE: probabilistic rho-algorithm of Pollard to find a factor of n in k loops.
     
    933933NOTE: Pollard's p-factorization
    934934       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|k
    936        then p devides gcd(a^k-1,n) for some random a
     935       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
    937937EXAMPLE:example pFactor; shows an example
    938938"
     
    974974         k for using the first k elements in B
    975975RETURN: a list of factors of n or the message: no divisor found
    976 NOTE: quadraticSieve: Idea is to find x,y such that x^2=y^2 mod n then
     976NOTE: The idea being used is to find x,y such that x^2=y^2 mod n then
    977977      gcd(x-y,n) can be a proper divisor of n
    978978EXAMPLE:example quadraticSieve; shows an example
     
    11281128"USAGE:  ellipticAdd(N,a,b,P,Q);
    11291129RETURN: 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 curve
     1130NOTE: P=(P[1]:P[2]:P[3]), Q=(Q[1]:Q[2]:Q[3]) points on the elliptic curve
    11311131      defined by y^2z=x^3+a*xz^2+b*z^3  over Z/N
    11321132EXAMPLE:example ellipticAdd; shows an example
     
    13501350RETURN: the number of points of the elliptic curve defined by
    13511351        y^2=x^3+a*x+b  over Z/N
    1352 NOTE: trivial aproach
     1352NOTE: trivial approach
    13531353EXAMPLE:example countPoints; shows an example
    13541354"
     
    14201420
    14211421proc ShanksMestre(number q, number a, number b, list #)
    1422 "USAGE:  ShanksMestre(q,a,b); optional:ShanksMestre(q,a,b,s); s the number
     1422"USAGE:  ShanksMestre(q,a,b); optional: ShanksMestre(q,a,b,s); s the number
    14231423         of loops in the algorithm (default s=1)
    14241424RETURN: the number of points of the elliptic curve defined by
    14251425         y^2=x^3+a*x+b  over Z/N
    1426 NOTE: algorithm of Shanks and Mestre (giant-step-baby-step)
     1426NOTE: algorithm of Shanks and Mestre (baby-step-giant-step)
    14271427EXAMPLE:example ShanksMestre; shows an example
    14281428"
     
    15751575"USAGE:  generateG(a,b,m);
    15761576RETURN: m-th division polynomial
    1577 NOTE: generate the recursively defined polynomials in Z[x,y],so called
    1578  division polynomials, p_m=generateG(a,b,m) such that on the elliptic curve
    1579  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  (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  m*P=0  iff p_m(P)=0
     1577NOTE: generate the so-called division polynomials, i.e., the recursively defined
     1578polynomials p_m=generateG(a,b,m) in Z[x, y] such that, for a point (x:y:1) on the
     1579elliptic curve defined by y^2=x^3+a*x+b  over Z/N the point@*
     1580m*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)
     1581and m*P=0  iff p_m(P)=0
    15821582EXAMPLE:example generateG; shows an example
    15831583"
     
    18461846         d+1 the number of loops in the algorithm (default d=0)
    18471847RETURN: a factor of N or the message no factor found
    1848 NOTE: - computes a factor of N using Lenstra's ECM factorization
     1848NOTE: - computes a factor of N using Lenstra's ECM factorization@*
    18491849      - the idea is that the fact that N is not prime is dedected using
    18501850        the operations on the elliptic curve
     
    19011901proc ECPP(number N)
    19021902"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)
     1903RETURN: 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)@*
    19061906         m,q integers
    19071907ASSUME: gcd(N,6)=1
Note: See TracChangeset for help on using the changeset viewer.