Singular

D.12.3 crypto_lib

Library:

crypto.lib

Purpose:

Procedures for teaching cryptography

Author:

Gerhard Pfister, pfister@mathematik.uni-kl.de

Overview:

The library contains procedures to compute the discrete logarithm, primality-tests, factorization included elliptic curves. The library is intended to be used for teaching purposes but not for serious computations. Sufficiently high printlevel allows to control each step, thus illustrating the algorithms at work.

Procedures:

D.12.3.1 decimal		number corresponding to the hexadecimal number s
D.12.3.2 eexgcdN		T with sum_i L[i]*T[i]=T[n+1]=gcd(L[1],...,L[n])
D.12.3.3 lcmN		compute lcm(a,b)
D.12.3.4 powerN		compute m^d mod n
D.12.3.5 chineseRem		compute x such that x = T[i] mod L[i]
D.12.3.6 Jacobi		the generalized Legendre symbol of a and n
D.12.3.7 primList		the list of all primes <=n
D.12.3.8 primL		first primes p_1,...,p_r such that q<p_1*...*p_r
D.12.3.9 intPart		the integral part of a rational number
D.12.3.10 intRoot		the integral part of the square root of m
D.12.3.11 squareRoot		the square root of a in Z/p, p prime
D.12.3.12 solutionsMod2		basis solutions of Mx=0 over Z/2
D.12.3.13 powerX		q-th power of the i-th variable modulo I
D.12.3.14 babyGiant		discrete logarithm x: b^x=y mod p
D.12.3.15 rho		discrete logarithm x: b^x=y mod p
D.12.3.16 MillerRabin		probabilistic primaly-test of Miller-Rabin
D.12.3.17 SolowayStrassen		probabilistic primaly-test of Soloway-Strassen
D.12.3.18 PocklingtonLehmer		primaly-test of Pocklington-Lehmer
D.12.3.19 PollardRho		Pollard's rho factorization
D.12.3.20 pFactor		Pollard's p-factorization
D.12.3.21 quadraticSieve		quadratic sieve factorization
D.12.3.22 isOnCurve		P is on the curve y^2z=x^3+a*xz^2+b*z^3 over Z/N
D.12.3.23 ellipticAdd		P+Q, addition on elliptic curves
D.12.3.24 ellipticMult		k*P on elliptic curves
D.12.3.25 ellipticRandomCurve		generates y^2z=x^3+a*xz^2+b*z^3 over Z/N randomly
D.12.3.26 ellipticRandomPoint		random point on y^2z=x^3+a*xz^2+b*z^3 over Z/N
D.12.3.27 countPoints		number of points of y^2=x^3+a*x+b over Z/N
D.12.3.28 ellipticAllPoints		points of y^2=x^3+a*x+b over Z/N
D.12.3.29 ShanksMestre		number of points of y^2=x^3+a*x+b over Z/N
D.12.3.30 Schoof		number of points of y^2=x^3+a*x+b over Z/N
D.12.3.31 generateG		m-th division polynomial of y^2=x^3+a*x+b over Z/N
D.12.3.32 factorLenstraECM		Lenstra's factorization
D.12.3.33 ECPP		primaly-test of Goldwasser-Kilian