Top
Back: ask
Forward: round
FastBack:
FastForward:
Up: Singular Manual
Top: Singular Manual
Contents: Table of Contents
Index: Index
About: About this document

D.12.2 crypto_lib

Library:
crypto.lib
Purpose:
Procedures for teaching cryptography
Authors:
Gerhard Pfister, pfister@mathematik.uni-kl.de
David Brittinger, dativ@gmx.net

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.2.1 round  rounds r to the nearest number in Z
D.12.2.2 bubblesort  sorts elements of the list L
D.12.2.3 decimal  number corresponding to the hexadecimal number s
D.12.2.4 eexgcdN  T with sum_i L[i]*T[i]=T[n+1]=gcd(L[1],...,L[n])
D.12.2.5 lcmN  compute lcm(a,b)
D.12.2.6 powerN  compute m^d mod n
D.12.2.7 chineseRem  compute x such that x = T[i] mod L[i]
D.12.2.8 Jacobi  the generalized Legendre symbol of a and n
D.12.2.9 primList  the list of all primes <=n
D.12.2.10 primL  first primes p_1,...,p_r such that q<p_1*...*p_r
D.12.2.11 intPart  the integral part of a rational number
D.12.2.12 intRoot  the integral part of the square root of m
D.12.2.13 squareRoot  the square root of a in Z/p, p prime
D.12.2.14 solutionsMod2  basis solutions of Mx=0 over Z/2
D.12.2.15 powerX  q-th power of the i-th variable modulo I
D.12.2.16 babyGiant  discrete logarithm x: b^x=y mod p
D.12.2.17 rho  discrete logarithm x: b^x=y mod p
D.12.2.18 MillerRabin  probabilistic primaly-test of Miller-Rabin
D.12.2.19 SolowayStrassen  probabilistic primaly-test of Soloway-Strassen
D.12.2.20 PocklingtonLehmer  primaly-test of Pocklington-Lehmer
D.12.2.21 PollardRho  Pollard's rho factorization
D.12.2.22 pFactor  Pollard's p-factorization
D.12.2.23 quadraticSieve  quadratic sieve factorization
D.12.2.24 isOnCurve  P is on the curve y^2z=x^3+a*xz^2+b*z^3 over Z/N
D.12.2.25 ellipticAdd  P+Q, addition on elliptic curves
D.12.2.26 ellipticMult  k*P on elliptic curves
D.12.2.27 ellipticRandomCurve  generates y^2z=x^3+a*xz^2+b*z^3 over Z/N randomly
D.12.2.28 ellipticRandomPoint  random point on y^2z=x^3+a*xz^2+b*z^3 over Z/N
D.12.2.29 countPoints  number of points of y^2=x^3+a*x+b over Z/N
D.12.2.30 ellipticAllPoints  points of y^2=x^3+a*x+b over Z/N
D.12.2.31 ShanksMestre  number of points of y^2=x^3+a*x+b over Z/N
D.12.2.32 Schoof  number of points of y^2=x^3+a*x+b over Z/N
D.12.2.33 generateG  m-th division polynomial of y^2=x^3+a*x+b over Z/N
D.12.2.34 factorLenstraECM  Lenstra's factorization
D.12.2.35 ECPP  primaly-test of Goldwasser-Kilian
D.12.2.36 calculate_ordering  Calculates x so that primitive^x == num1 mod mod1
D.12.2.37 is_primitive_root  Checks if primitive is a primitive root modulo mod1
D.12.2.38 find_first_primitive_root  Returns the first primitive root modulo mod1, starting with 1
D.12.2.39 binary_add  Adds a 1 to a binary encoded list
D.12.2.40 inverse_modulus  Finds a t so that t*num = 1 mod mod1
D.12.2.41 is_prime  Checks if n is prime proc find_biggest_index(a) Returns the index of the biggest element of a
D.12.2.42 find_index  Returns the list index of element e in list a. Returns 0 if e is not in a
D.12.2.43 subset_sum01  solves the subset-sum-knapsack-problem by calculating all subsets and choosing the right solution
D.12.2.44 subset_sum02  solves the subset-sum-knapsack-problem with a naive greedy algorithm
D.12.2.45 unbounded_knapsack  solves the unbounded_knapsack-problem, needing a list of knapsack weights, a list of profits and a capacity
D.12.2.46 multidimensional_knapsack  solves the multidimensional_knapsack-problem by using the PECH algorithm, needing a weight matrix m, a list of capacities and a list of profits
D.12.2.47 naccache_stern_generation  generates a hard knapsack for the Naccache-Stern Kryptosystem for given key and prime modulus
D.12.2.48 naccache_stern_encryption  encrypts a message with the Naccache-Stern Kryptosystem, using a hard knapsack, a message encoded as binary list and a prime modulus
D.12.2.49 naccache_stern_decryption  decrypts a message with the Naccache-Stern Kryptosystem, using the easy knapsack, the key, the prime modulus and the message encoded as integer
D.12.2.50 m_merkle_hellman_transformation  generates a hard knapsack for the multiplicative Merkle-Hellman Kryptosystem for a given easy knapsack and a primitive root for a modulus mod1
D.12.2.51 m_merkle_hellman_encryption  encrypts a message with the multiplicative Merkle-Hellman Kryptosystem, using a hard knapsack and a message encoded as binary list
D.12.2.52 m_merkle_hellman_decryption  decrypts a message with the multiplicative Merkle-Hellman Kryptosystem, using the easy knapsack, the key given by the primitive root, the modulus mod1 and the message encoded as integer merkle_hellman_transformation(list knapsack, int key, int mod1 generates a hard knapsack for the Merkle-Hellman Kryptosystem for a given easy knapsack , a multiplicator key and a modulus mod1
D.12.2.53 merkle_hellman_encryption  encrypts a message with the Merkle-Hellman Kryptosystem, using a hard knapsack and a message encoded as binary list
D.12.2.54 merkle_hellman_decryption  decrypts a message with the multiplicative Merkle-Hellman Kryptosystem, using the hard knapsack, the key, the modulus mod1 and the message encoded as integer
D.12.2.55 super_increasing_knapsack  Creates the smallest super-increasing knapsack of given size ksize
D.12.2.56 h_increasing_knapsack  Creates the smallest h-increasing knapsack of given size ksize and h
D.12.2.57 injective_knapsack  Creates all list of all injective knapsacks of given size ksize and maximal element kmaxelement
D.12.2.58 calculate_max_sum  Calculates the maximal sum of a given knapsack a
D.12.2.59 set_is_injective  Checks if knapsack a is injective
D.12.2.60 is_h_injective  Checks if knapsack a is h-injective
D.12.2.61 is_fix_injective  Checks if knapsack a is fix-injective
D.12.2.62 three_elements  Creates the smallest injective knapsack with a given injective_knapsack by using the three-elements-algorithm with a given number of iterations


Top Back: ask Forward: round FastBack: FastForward: Up: Singular Manual Top: Singular Manual Contents: Table of Contents Index: Index About: About this document
            User manual for Singular version 4.3.1, 2022, generated by texi2html.