CrackingCodes.Ch22 package

Submodules

CrackingCodes.Ch22.PracticeQuestions module

Chapter 22 Practice Questions

Answers Chapter 22 Practice Questions via Python code.

CrackingCodes.Ch22.PracticeQuestions.main()[source]

CrackingCodes.Ch22.primeNum module

Prime Number Sieve

Implements a series of functions that determine if a given number is prime.

CrackingCodes.Ch22.primeNum.LOW_PRIMES

List containing prime numbers <= 100 (aka ‘low primes’).

Type:list

Note

CrackingCodes.Ch22.primeNum.generateLargePrime(keysize: int = 1024) → int[source]

Generate large prime number

Generates random numbers of given bit size until one is prime.

Parameters:keysize – Number of bits prime number should be.
Returns:Random prime number that is keysize bits in size.

Note

  • keysize defaults to 1024 bits.
CrackingCodes.Ch22.primeNum.isPrime(num: int) → bool[source]

Is prime

This function checks divisibility by LOW_PRIMES before calling rabinMiller().

Parameters:num – Integer to check if prime.
Returns:True if num is prime, False otherwise.

Note

  • If a number is divisible by a low prime number, it is not prime.
CrackingCodes.Ch22.primeNum.isPrimeTrialDiv(num: int) → bool[source]

Is prime trial division

Uses the trial division algorithm for testing if a given number is prime.

Parameters:num – Integer to determine if prime.
Returns:True if num is a prime number, otherwise False.
CrackingCodes.Ch22.primeNum.primeSieve(sieveSize: int) → list[source]

Prime sieve

Calculates prime numbers using the Sieve of Eratosthenes algorithm.

Parameters:sieveSize – Largest number to check if prime starting from zero.
Returns:List containing prime numbers from 0 to given number.
CrackingCodes.Ch22.primeNum.rabinMiller(num: int) → bool[source]

Rabin-Miller primality test

Uses the Rabin-Miller primality test to check if a given number is prime.

Parameters:num – Number to check if prime.
Returns:True if num is prime, False otherwise.

Note

  • The Rabin-Miller primality test relies on unproven assumptions, therefore it can return false positives when given a pseudoprime.

Module contents