### 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

User manual for Singular version 4.4.1, 2025, generated by texi2html.