alkulukugeneraattori.py

# Ohjelma generoi suuren bittimääräältään halutukokoisen käyttäen
# alkuluvun testauksessa käytetään Miller-Rabinin menetelmään
# joka on virheetön lukua 341550071728321 pienemmille
# ja sitä suuremmille virheen mahdollisuus äärimmäisen pieni
# suuria alkulukuja käytetään julkisen avaimen salauksessa
# ohjelma tehty käyttäen lähdettä https://inventwithpython.com/hacking/chapter23.html
# Juhani Kaukoranta 29.3.2019

import random
import math
import time
# numba nopeuttaa laskentaa pitkillä salasanoilla
# halutessasi voit poistaa risuaidan alla olevista 'from numba import jit' ja '@jit(parallel=True)'
#from numba import jit

# *** Pääohjelman käyttämät funktiot ***

# alkuluvun generointi käyttäen annettua bittipituutta
#@jit(parallel=True)
def generateLargePrime(keysize):
    # Return a random prime number of keysize bits in size.
    while True:
        num = random.randrange(2**(keysize-1), 2**(keysize))
        if is_prime(num):
            return num

# Miller-Rabin correct and probabilistic composite, prime test
# correct answers for n less than 341550071728321
# and then reverting to the probabilistic form
# source https://rosettacode.org/wiki/Miller%E2%80%93Rabin_primality_test#Python

def _try_composite(a, d, n, s):
    if pow(a, d, n) == 1:
        return False
    for i in range(s):
        if pow(a, 2**i * d, n) == n-1:
            return False
    return True # n  is definitely composite

def is_prime(n, _precision_for_huge_n=16):
     # _known_lowprimes are primes < 1000


    if n in _known_lowprimes:
        return True
    if any((n % p) == 0 for p in _known_lowprimes) or n in (0, 1):
        return False
    d, s = n - 1, 0
    while not d % 2:
        d, s = d >> 1, s + 1
    # Returns exact according to http://primes.utm.edu/prove/prove2_3.html
    if n < 1373653:
        return not any(_try_composite(a, d, n, s) for a in (2, 3))
    if n < 25326001:
        return not any(_try_composite(a, d, n, s) for a in (2, 3, 5))
    if n < 118670087467:
        if n == 3215031751:
            return False
        return not any(_try_composite(a, d, n, s) for a in (2, 3, 5, 7))
    if n < 2152302898747:
        return not any(_try_composite(a, d, n, s) for a in (2, 3, 5, 7, 11))
    if n < 3474749660383:
        return not any(_try_composite(a, d, n, s) for a in (2, 3, 5, 7, 11, 13))
    if n < 341550071728321:
        return not any(_try_composite(a, d, n, s) for a in (2, 3, 5, 7, 11, 13, 17))
    # otherwise
    return not any(_try_composite(a, d, n, s)
                   for a in _known_lowprimes[:_precision_for_huge_n])

# lasketaan valmiiksi _known_lowprimes eli alkuluvut < 1000
# nopeuttaa huomattavasti tarkistusta, onko luku alkuluku
_known_lowprimes = [2, 3]
_known_lowprimes += [x for x in range(5, 1000, 2) if is_prime(x)]
# *** Pääohjelma ***
print("Ohjelma generoi bittimäärältään halutunkokoisen alkuluvun")
bittipituus = int(input("Anna salaukseen haluttu bittimäärä, esim 256, 512,1024,2048 "))
time0 = time.perf_counter()
alkuluku = generateLargePrime(bittipituus)
time1 = time.perf_counter()
print("Annettu bittipituus oli ",bittipituus)
print("Generoitu alkuluku on ",alkuluku)
print("Alkulukuvun pituus on ",len(str(alkuluku))," numeroa")
print("Tarkistus alkuluvun bittisyydelle: ", math.log(alkuluku,2))
print("Laskenta-aika oli ",time1-time0," sekuntia")