pratt_25519_certificate.py

# http://www.russinoff.com/papers/pratt.pdf

import math

number = 2**255 - 19
certificate = [2,
 [2, 3, 65147, 74058212732561358302231226437062788676166966415465897661863160754340907],
 [2, 1, 1, 1],
 [[], [], [],
  [2,
   [2, 3, 353, 57467, 132049, 1923133, 31757755568855353, 75445702479781427272750846543864801],
   [1, 1, 1, 1, 1, 1, 1, 1],
   [[], [], [], [], [], [],
    [10,
     [2, 3, 31, 107, 223, 4153, 430751],
     [3, 1, 1, 1, 1, 1, 1],
     [[], [], [], [], [], [], []]],
    [7,
     [2, 3, 5, 75707, 72106336199, 1919519569386763],
     [5, 2, 2, 1, 1, 1],
     [[], [], [], [],
      [17,
       [2, 13, 2773320623],
       [1, 1, 1],
       [[], [],
        [5,
         [2, 2437, 569003],
         [1, 1, 1],
         [[], [], []]]]],
      [2,
       [2, 3, 7, 19, 47, 127, 8574133],
       [1, 1, 1, 1, 2, 1, 1],
       [[], [], [], [], [], [], []]]]]]]]]

def bruteforce_primality_check(number):
    limit = int(math.sqrt(float(number))) + 1
    limit = min(number, limit)
    for i in range(2, limit):
        if number % i == 0:
            raise Exception('found factor for {}: {}'.format(number, i))

def check_certificate(number, certificate=None):
    if not certificate or len(certificate) == 0:
        assert number < 10_000_000, \
            'number without certificate is too big: {}'.format(number)
        bruteforce_primality_check(number)
        return

    [root, factors, powers, children] = certificate

    sub1 = number - 1
    product = 1
    for (factor, power) in zip(factors, powers):
        assert factor > 1, 'factor too small: {}!'.format(factor)
        assert power > 0, 'power too small: {}!'.format(power)
        product *= factor ** power

    assert sub1 == product, \
            'factorization doesnt match: {} != {}'.format(sub1, product)

    assert pow(root, number - 1, number) == 1, \
            'invalid root: {}^({} - 1) mod {} != 1'.format(root, number, number)

    for factor in factors:
        assert sub1 % factor == 0, \
                'bad factor: {} % {} != 0'.format(sub1, factor)
        assert pow(root, sub1 // factor, number) != 1, \
                'bad root: {}^({}/{}) == 1'.format(root, sub1, factor)

    for (factor, child) in zip(factors, children):
        check_certificate(factor, child)

check_certificate(number, certificate)