The primes module

primes.chop_integer(m, n)

Chop a large integer m into integer packets, where each packet has at most n digits

Example:

>>> chop_integer(123451234512345,5)
[12345, 12345, 12345]

primes.chop_message(m, n)

Chop message m it into packets of at most n characters

Example:

>>> chop_message("This is a not so long message!",10)
['This is a ', 'not so lon', 'g message!']

primes.davis_dec(x)

Davis table decoding (from numbers to letters)

Outputs:

The message (str) encoded in x

see http://mathcircle.berkeley.edu/BMC3/crypto.pdf

Example:

>>> davis_dec(184148485170)
'Hello!'

primes.davis_enc(m)

Davis table encoding (from letters to numbers)

Outputs:

A large integer with an even number of digits

see http://mathcircle.berkeley.edu/BMC3/crypto.pdf

Example:

>>> davis_enc("Hello!")
184148485170

primes.decode_message(em)

Decode a list of integer packets into a message (using Davis table, see davis_dec())

Example:

>>> print decode_message([30444555104555103710L, 50515610555110485150L, 43104941555537434170L])
This is a 
not so lon
g message!

primes.egcd(a, b)

Carries out extended Euclid’s algorithm on a and b.

Outputs:

x, y integers such that \(ax+by = \text{gcd}(a,b)\)

How does this work? Assuming \(a\geq b\), the integer division gives

\(a = bq+r\)

If \(r=0\) then we are done since gcd(a,b) = b if not we have

\(\Rightarrow \text{gcd}(a,b) = \text{gcd}(b,r)\)

For the extended gcd part, if \(r=0\) we certainly have \(b = \text{gcd}(a,b) = a \cdot 0 + b \cdot 1\). Otherwise, if we know that \(bx + ry = \text{gcd}(b,r) = \text{gcd}(a,b)\), we must have that

\(\text{gcd}(a,b) = bx + ry = bx + (a-bq)y = ay + (x-qy)b\)

Example:

>>> egcd(880,560)
(80, 2, -3)

primes.encode_message(m, n)

Encode message m with packets of at most 2 n digits integers (using Davis table, see davis_enc())

Example:

>>> encode_message("This is a not so long message!",10)
[30444555104555103710L, 50515610555110485150L, 43104941555537434170L]

primes.is_probable_prime(n)

Miller-Rabin primality test.

A return value of False means n is certainly not prime. A return value of True means n is very likely a prime.

This code comes from: http://rosettacode.org/wiki/Miller-Rabin_primality_test#Python (with corrections!)

Example:

>>> is_probable_prime(50800665469)
True
>>> is_probable_prime(2**1279 -1)
True

primes.join_integer(l)

Joins a large integer that has been chopped in a list

Example:

>>> join_integer([1234567,8910111213,141516171819])
12345678910111213141516171819L

primes.modinv(a, n)

Computes the multiplicative inverse of a modulo n. For the multiplcative inverse to exist, we must have \(\text{gcd}(a,n)=1\)

Outputs:

x integer such that \(ax \mod n = 1\)

Example:

>>> modinv(17,880)
673

primes.randprime(ndigits)

Generate a prime number with ndigits digits

Example:

>>> randprime(10)
50800665469

primes.rsa_check(p, q, N, N2, e, d, ndigits)

Do some checks on some RSA numbers. The numbers p,q,N,N2,e,d could come from rsa_gen()

Example:

>>> status,msg = rsa_check(23,41,943,880,17,503,1)
>>> print str(status)+" "+msg
False The following diagnostics failed:
  e and d are not multiplicative inverses of each other
  problem in enc/dec
>>> status,msg = rsa_check(23,41,943,880,17,673,1)
>>> print str(status)+" "+msg
True All tests passed!
  N  has 3 digits
  N2 has 3 digits