Gecko [ www.leshallesdegournay.geraud-market.com ]

Name	Size	Permission	Date
__init__.py	1.44 KB	-rw-r--r--	2016-03-26 13:34
__init__.pyc	1.08 KB	-rw-r--r--	2016-03-26 19:02
__init__.pyo	1.08 KB	-rw-r--r--	2016-03-26 19:02
_compat.py	3.8 KB	-rw-r--r--	2016-03-26 13:30
_compat.pyc	3.55 KB	-rw-r--r--	2016-03-26 19:02
_compat.pyo	3.55 KB	-rw-r--r--	2016-03-26 19:02
_version133.py	11.49 KB	-rw-r--r--	2016-03-26 13:31
_version133.pyc	13.23 KB	-rw-r--r--	2016-03-26 19:02
_version133.pyo	13.23 KB	-rw-r--r--	2016-03-26 19:02
_version200.py	14.77 KB	-rw-r--r--	2016-03-26 13:31
_version200.pyc	14.76 KB	-rw-r--r--	2016-03-26 19:02
_version200.pyo	14.76 KB	-rw-r--r--	2016-03-26 19:02
asn1.py	1.74 KB	-rw-r--r--	2016-03-26 13:30
asn1.pyc	1.61 KB	-rw-r--r--	2016-03-26 19:02
asn1.pyo	1.61 KB	-rw-r--r--	2016-03-26 19:02
bigfile.py	5.06 KB	-rw-r--r--	2016-03-26 13:31
bigfile.pyc	4.67 KB	-rw-r--r--	2016-03-26 19:02
bigfile.pyo	4.67 KB	-rw-r--r--	2016-03-26 19:02
cli.py	11.9 KB	-rw-r--r--	2016-03-26 13:31
cli.pyc	12.76 KB	-rw-r--r--	2016-03-26 19:02
cli.pyo	12.76 KB	-rw-r--r--	2016-03-26 19:02
common.py	4.53 KB	-rw-r--r--	2016-03-26 13:30
common.pyc	4.11 KB	-rw-r--r--	2016-03-26 19:02
common.pyo	4.11 KB	-rw-r--r--	2016-03-26 19:02
core.py	1.62 KB	-rw-r--r--	2016-03-26 13:30
core.pyc	1.44 KB	-rw-r--r--	2016-03-26 19:02
core.pyo	1.44 KB	-rw-r--r--	2016-03-26 19:02
key.py	22.33 KB	-rw-r--r--	2016-03-26 13:31
key.pyc	23.36 KB	-rw-r--r--	2016-03-26 19:02
key.pyo	23.36 KB	-rw-r--r--	2016-03-26 19:02
parallel.py	2.25 KB	-rw-r--r--	2016-03-26 13:30
parallel.pyc	2.01 KB	-rw-r--r--	2016-03-26 19:02
parallel.pyo	2.01 KB	-rw-r--r--	2016-03-26 19:02
pem.py	3.45 KB	-rw-r--r--	2016-03-26 13:31
pem.pyc	2.75 KB	-rw-r--r--	2016-03-26 19:02
pem.pyo	2.75 KB	-rw-r--r--	2016-03-26 19:02
pkcs1.py	11.94 KB	-rw-r--r--	2016-03-26 13:31
pkcs1.pyc	10.87 KB	-rw-r--r--	2016-03-26 19:02
pkcs1.pyo	10.83 KB	-rw-r--r--	2016-03-26 19:02
prime.py	4.45 KB	-rw-r--r--	2016-03-26 13:31
prime.pyc	3.54 KB	-rw-r--r--	2016-03-26 19:02
prime.pyo	3.49 KB	-rw-r--r--	2016-03-26 19:02
randnum.py	2.58 KB	-rw-r--r--	2016-03-26 13:30
randnum.pyc	2.01 KB	-rw-r--r--	2016-03-26 19:02
randnum.pyo	2.01 KB	-rw-r--r--	2016-03-26 19:02
transform.py	6.73 KB	-rw-r--r--	2016-03-26 13:30
transform.pyc	5.67 KB	-rw-r--r--	2016-03-26 19:02
transform.pyo	5.67 KB	-rw-r--r--	2016-03-26 19:02
util.py	2.99 KB	-rw-r--r--	2016-03-26 13:30
util.pyc	2.38 KB	-rw-r--r--	2016-03-26 19:02
util.pyo	2.3 KB	-rw-r--r--	2016-03-26 19:02
varblock.py	5.28 KB	-rw-r--r--	2016-03-26 13:31
varblock.pyc	4.7 KB	-rw-r--r--	2016-03-26 19:02
varblock.pyo	4.7 KB	-rw-r--r--	2016-03-26 19:02

Rename

# -*- coding: utf-8 -*-
#
#  Copyright 2011 Sybren A. Stüvel <sybren@stuvel.eu>
#
#  Licensed under the Apache License, Version 2.0 (the "License");
#  you may not use this file except in compliance with the License.
#  You may obtain a copy of the License at
#
#      https://www.apache.org/licenses/LICENSE-2.0
#
#  Unless required by applicable law or agreed to in writing, software
#  distributed under the License is distributed on an "AS IS" BASIS,
#  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
#  See the License for the specific language governing permissions and
#  limitations under the License.

"""Numerical functions related to primes.

Implementation based on the book Algorithm Design by Michael T. Goodrich and
Roberto Tamassia, 2002.
"""

import rsa.randnum

__all__ = ['getprime', 'are_relatively_prime']

def gcd(p, q):
    """Returns the greatest common divisor of p and q

>>> gcd(48, 180)
    12
    """

while q != 0:
        (p, q) = (q, p % q)
    return p

def miller_rabin_primality_testing(n, k):
    """Calculates whether n is composite (which is always correct) or prime
    (which theoretically is incorrect with error probability 4**-k), by
    applying Miller-Rabin primality testing.

For reference and implementation example, see:
    https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test

:param n: Integer to be tested for primality.
    :type n: int
    :param k: Number of rounds (witnesses) of Miller-Rabin testing.
    :type k: int
    :return: False if the number is composite, True if it's probably prime.
    :rtype: bool
    """

# prevent potential infinite loop when d = 0
    if n < 2:
        return False

# Decompose (n - 1) to write it as (2 ** r) * d
    # While d is even, divide it by 2 and increase the exponent.
    d = n - 1
    r = 0

while not (d & 1):
        r += 1
        d >>= 1

# Test k witnesses.
    for _ in range(k):
        # Generate random integer a, where 2 <= a <= (n - 2)
        a = rsa.randnum.randint(n - 4) + 2

x = pow(a, d, n)
        if x == 1 or x == n - 1:
            continue

for _ in range(r - 1):
            x = pow(x, 2, n)
            if x == 1:
                # n is composite.
                return False
            if x == n - 1:
                # Exit inner loop and continue with next witness.
                break
        else:
            # If loop doesn't break, n is composite.
            return False

return True

def is_prime(number):
    """Returns True if the number is prime, and False otherwise.

>>> is_prime(2)
    True
    >>> is_prime(42)
    False
    >>> is_prime(41)
    True
    >>> [x for x in range(901, 1000) if is_prime(x)]
    [907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997]
    """

# Check for small numbers.
    if number < 10:
        return number in [2, 3, 5, 7]

# Check for even numbers.
    if not (number & 1):
        return False

# According to NIST FIPS 186-4, Appendix C, Table C.3, minimum number of
    # rounds of M-R testing, using an error probability of 2 ** (-100), for
    # different p, q bitsizes are:
    #   * p, q bitsize: 512; rounds: 7
    #   * p, q bitsize: 1024; rounds: 4
    #   * p, q bitsize: 1536; rounds: 3
    # See: http://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.186-4.pdf
    return miller_rabin_primality_testing(number, 7)

def getprime(nbits):
    """Returns a prime number that can be stored in 'nbits' bits.

>>> p = getprime(128)
    >>> is_prime(p-1)
    False
    >>> is_prime(p)
    True
    >>> is_prime(p+1)
    False

>>> from rsa import common
    >>> common.bit_size(p) == 128
    True
    """

assert nbits > 3  # the loop wil hang on too small numbers

while True:
        integer = rsa.randnum.read_random_odd_int(nbits)

# Test for primeness
        if is_prime(integer):
            return integer

# Retry if not prime

def are_relatively_prime(a, b):
    """Returns True if a and b are relatively prime, and False if they
    are not.

>>> are_relatively_prime(2, 3)
    True
    >>> are_relatively_prime(2, 4)
    False
    """

d = gcd(a, b)
    return d == 1

if __name__ == '__main__':
    print('Running doctests 1000x or until failure')
    import doctest

for count in range(1000):
        (failures, tests) = doctest.testmod()
        if failures:
            break

if count and count % 100 == 0:
            print('%i times' % count)

print('Doctests done')