Number Theory Package Documentation

Welcome to the documentation for the num_theory package! This package provides essential number theory functions designed for educational and analytical purposes. From prime factorization to generating arithmetic progressions, the num_theory package is a versatile tool for students, researchers, and enthusiasts alike. It can also serve as a utility for developing solutions to Project Euler problems.

Installation

To begin using the num_theory package, you can install it using the following pip command in your bash terminal:

pip install num_theory

Once installed, you can import the package in your Python project:

import num_theory

print(num_theory.__version__)

0.2.7

You may also choose to import num_theory functions individually:

from num_theory import prime_factorization
from num_theory import arithmetic_progression
from num_theory import get_primes
from num_theory import is_prime

Prime Factorization

The prime_factorization function breaks down a number into its prime components, which is especially useful for understanding number properties, simplifying fractions, and studying cryptographic algorithms.

How It Works

The function determines prime factors using the following steps:

  1. Start by dividing the number by 2 (the smallest prime) and record how many times it divides evenly.

  2. Proceed to odd numbers (3, 5, etc.) and repeat the division process, recording the results.

  3. Stop when the divisor squared exceeds the given number. If a remainder greater than 1 remains, it is also a prime factor.

Parameters

n : int
The integer to factorize. Must be a positive integer greater than 1.

Example Usage

Here are some examples to demonstrate the prime_factorization function:

from num_theory.prime_factorization import prime_factorization

# Factorizing 28
print(prime_factorization(28))  
# Output: [(2, 2), (7, 1)] which is equal to (2^2 + 7^1 = 28)

# Factorizing 100
print(prime_factorization(100)) 
# Output: [(2, 2), (5, 2)] which is equal to (2^2 + 5^2 = 100)

Real-Life Applications

Application 1: Simplifying Fractions

A student learning fractions wants to simplify the fraction 28/35. Using the prime_factorization function, they can find the prime factors of both the numerator and denominator, then divide by their greatest common divisor (GCD):

from num_theory.prime_factorization import prime_factorization

def simplify_fraction(numerator, denominator):
    num_factors = prime_factorization(numerator)
    den_factors = prime_factorization(denominator)
    gcd = 1
    for factor, _ in num_factors:
        if factor in dict(den_factors):
            gcd *= factor
    return numerator // gcd, denominator // gcd

# Simplify 28/35
print(simplify_fraction(28, 35))  # Output: (4, 5)

(4, 5)

Application 2: Finding Multiples in a Classroom Activity

A teacher wants to create a fun activity where students identify the prime factors of numbers between 2 and 10. The prime_factorization function can generate the factors for any number:

# Prime factors for classroom activity
for num in range(2, 11):
    print(f"{num}: {prime_factorization(num)}")

2: [(2, 1)]
3: [(3, 1)]
4: [(2, 2)]
5: [(5, 1)]
6: [(2, 1), (3, 1)]
7: [(7, 1)]
8: [(2, 3)]
9: [(3, 2)]
10: [(2, 1), (5, 1)]

This activity helps students visually understand how numbers break down into prime components.

Application 3: Cryptographic Key Analysis

A cybersecurity researcher is investigating the factorization of large integers as part of a study on cryptographic algorithms, specifically RSA encryption. The security of RSA relies on the difficulty of factoring the product of two large prime numbers. To demonstrate this concept, the researcher uses the prime_factorization function to:

  1. Factorize smaller integers to explain the concept of prime factorization to a team of non-technical stakeholders.

  2. Test and validate a set of randomly generated composite numbers to confirm their factorization as part of the cryptographic key analysis process.

  3. Analyze the distribution of prime factors in datasets of composite numbers to study patterns or anomalies that may reveal vulnerabilities in certain key-generation techniques.

This function serves as an educational tool and a basic analysis tool for smaller numbers, helping the researcher communicate and validate fundamental cryptographic concepts.

Example Usage

from num_theory.prime_factorization import prime_factorization

# Example 1: Factorizing 28
print(prime_factorization(28))  # Output: [(2, 2), (7, 1)]

# Example 2: Factorizing 100
print(prime_factorization(100))  # Output: [(2, 2), (5, 2)]

# Example 3: Factorizing 13195
print(prime_factorization(13195))  # Output: [(5, 1), (7, 1), (13, 1), (29, 1)]

[(2, 2), (7, 1)]
[(2, 2), (5, 2)]
[(5, 1), (7, 1), (13, 1), (29, 1)]

Additional Notes

  1. Edge Cases:

    • Input validation ensures non-integers and integers <= 1 raise an error.

  2. Performance:

    • Efficient for small numbers.

    • May be slow for very large numbers due to the use of trial division.

    • This algorithm has a time complexity of O(√n) and a space complexity of O(log(n)).

  3. Future Improvements:

    • Implement more advanced factorization algorithms for better performance on large inputs.

Get Primes

The get_primes function generates a list of all prime numbers below a given integer. This is ideal for applications like solving Project Euler problems, creating hashing methods, and studying prime number distributions.

How it works

The get_primes() function uses a custom Sieve of Eratosthenes algorithm to retrieve the list of prime numbers. It does this in the following steps:

  1. Create a list of booleans of size n.

  2. Initialize all booleans in the list as True.

  3. Starting from 2, iterate in ascending order through all numbers under n.

  4. In our boolean list, assign the index corresponding to every number’s multiples as False (non-prime).

  5. Return a list containing only prime numbers.

Sieve of Eratosthenes Animation

Figure 1: An animation demonstrating the Sieve of Eratosthenes. Created by SKopp and distributed under the GNU Free Documentation License 1.3.

Parameters

n : int
The number to find primes under. Can be any non-negative number.

Real-World Applications

Application 1: Generating Prime-Based Security Codes

A small business wants to generate unique security codes using prime numbers for encrypting customer IDs. Using the get_primes function, they generate primes up to a certain number and select them as secure keys:

from num_theory.get_primes import get_primes

# Generate prime-based security codes
security_codes = get_primes(100)
print(security_codes) 

[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]

Application 2: Project Euler’s prime numbers sum.

Project Euler’s 10th problem states: “Find the sum of all the primes below two million.” Using our get_primes() function trivializes this problem, as we can simply use Python’s built-in sum() function along with our function, passing 2,000,000 as the argument. Our function will retrieve the list of all primes under 2,000,000, and sum() will calculate their sum to obtain the answer.

from num_theory.get_primes import get_primes

# Sum of all primes below 2,000,000
print(sum(get_primes(2000000)))

142913828922

Application 3: Hashing with Primes

Suppose you want to create a simple hash function that converts a given number into a value within the range of 0 to 255. You can achieve this by using the modulo (%) operation along with the sum of the output from our get_primes() function to create a straightforward hashing algorithm. However, please note that this hashing function is extremely rudimentary and not suitable for most practical applications, it is used here solely as an easy-to-understand example.

def simple_hash(num: int) -> int:
    from num_theory.get_primes import get_primes
    return sum(get_primes(num)) % 256

print(simple_hash(2025))
print(simple_hash(1999))

201
58

Additional notes

  1. Edge cases:

    • This function will return an empty list for negative numbers, 0, and 1.

    • This function accepts fractional numbers but floors them so get_primes(10.8) is equivalent to get_primes(10)

  2. Performance:

    • This algorithm has a time complexity of O(n ⋅ log(log(n))) and a space complexity of O(n).

    • The get_primes() function uses a custom Sieve of Eratosthenes algorithm to retrieve the list of prime numbers. It does this by initializing a list of all number under n, then it iterates through all of them from the bottom to the top and assigns their multiples as non-primes. Once done, it leaves you with a list containing only prime numbers under n.

  3. Future improvements:

    • This function’s utility could be improved through additional functionalities that can be selected through parameters (e.g., return the list reversed or return just the largest prime under n).

    • The algorithm can be further optimized using Segmented sieve.

Arithmetic Progression

The arithmetic_progression function calculates terms, sums, or sequences of arithmetic progressions. This can model savings plans, salary increments, and more.

How it works

Default:

  1. Iterate through n steps.

  2. For each step, multiply the number of steps taken with the difference between terms and add it to the first term.

  3. Append each calculated term to a list and return the list when finished.

Compute sum:

  1. Calculate the sum of n terms directly using the following formula: Compute Sum Formula

Nth term:

  1. Calculate the nth term directly using the following formula: nth term Formula

Parameters

a : float
The first term of the AP.
d : float
The common difference between consecutive terms.
n : int
The number of terms, the term to compute, or the term index.
compute_sum : bool, optional
If True, computes the sum of the first n terms. Default is False.
nth_term : bool, optional
If True, computes the nth term of the AP instead of generating terms. Default is False.

Example 1: Saving for a Vacation

You start saving $100 in the first month, increasing by $10 each month. Let’s calculate:

  1. Total savings after 12 months.

  2. Amount saved in the 12th month.

  3. The savings progression.

from num_theory.arithmetic_progression import arithmetic_progression

# Total savings after 12 months
print(f"Total savings after 12 months: ${arithmetic_progression(a=100, d=10, n=12, compute_sum=True):,}") 

# Amount saved in the 12th month
print(f"Amount saved in the 12th month: ${arithmetic_progression(a=100, d=10, n=12, nth_term=True):,}") 

# Savings progression
print(arithmetic_progression(a=100, d=10, n=12))

Total savings after 12 months: $1,860.0
Amount saved in the 12th month: $210
[100, 110, 120, 130, 140, 150, 160, 170, 180, 190, 200, 210]

Example 2: Salary Increment

Your starting salary is $50,000, with an annual increment of $3,000. Let’s calculate:

  1. Salary in the 5th year.

  2. Total earnings over 5 years.

  3. Salary progression over 5 years.

# Salary in the 5th year
print(f"Salary in the 5th year: ${arithmetic_progression(a=50000, d=3000, n=5, nth_term=True):,}") 

# Total earnings over 5 years
print(f"Total earnings over 5 years: ${arithmetic_progression(a=50000, d=3000, n=5, compute_sum=True):,}")

# Salary progression over 5 years
print(arithmetic_progression(a=50000, d=3000, n=5))  # Output: [50000, 53000, ..., 62000]

Salary in the 5th year: $62,000
Total earnings over 5 years: $280,000.0
[50000, 53000, 56000, 59000, 62000]

Additional notes

  1. Edge cases:

    • This function will raise an error if any of its integer parameters are fed with non-integers.

    • This function will also raise an error if the number of terms is a negative number.

  2. Performance:

    • This function has a time complexity of O(n) and a space complexity of O(n).

    • compute_sum has a time complexity of O(1) and a space complexity of O(1).

    • nth_term has a time complexity of O(1) and a space complexity of O(1).

  3. Future improvements:

    • This function’s interpretability with large values of n can be enhanced using visualizations such as line charts.

    • Additional options to calculate exponential growth and other non linear progressions (e.g., geometric, harmonic, etc.).

Is Prime

The is_prime function provides a simple, efficient, and reliable way to determine whether a given integer is prime. This lightweight utility is perfect for educational purposes, mathematical explorations, and real-world applications requiring prime number checks.

How it works

  1. Return True if n is 2, return False if n is an even number greater than 2.

  2. Check odd divisors from 3 to sqrt(n) for any that evenly divide n.

  3. Return True if no divisors are found.

Parameters

n : int
The number to check for primality. Must be a positive integer greater than 1.

Example Usage

from num_theory.is_prime import is_prime

print(is_prime(7))  # True
print(is_prime(10))  # False

Application 1: Cryptography & Security PIN Validation

In cryptography, prime numbers are widely used for secure encryption. A system might validate that a chosen PIN is prime before accepting it as secure.

from num_theory.is_prime import is_prime
pin = 53
if is_prime(pin):
    print(f"PIN {pin} is accepted as it's a prime number—secure and unique!")
else:
    print(f"PIN {pin} is rejected. Please choose a prime number.")
# Output: PIN 53 is accepted as it's a prime number—secure and unique!

PIN 53 is accepted as it's a prime number—secure and unique!

Application 2: Unique Classroom Groups

A teacher wants to divide students into groups of a size that is prime, ensuring groups are small and effective.

group_size = 7
if is_prime(group_size):
    print(f"Group size {group_size} works! It's prime, so students will interact uniquely.")
else:
    print(f"Group size {group_size} isn't prime. Let's try a different size.")
# Output: Group size 7 works! It's prime, so students will interact uniquely.

Group size 7 works! It's prime, so students will interact uniquely.

Application 3: Generate RSA Keys

In encryption applications, generating an RSA key pair (public and private keys) requires two large prime numbers and modulus calculations. This code uses is_prime to verify the generated prime numbers and constructs the RSA public and private keys, showcasing a practical application in a real-world encryption system.

import random
from math import gcd

# Generate large primes
def generate_large_prime(start, end):
    while True:
        n = random.randint(start, end)
        if is_prime(n):
            return n

# Generate RSA keys
def generate_rsa_keys():
    p = generate_large_prime(100, 999)
    q = generate_large_prime(100, 999)
    n = p * q
    phi = (p - 1) * (q - 1)

    # Choose e such that 1 < e < phi and gcd(e, phi) = 1
    e = random.choice([x for x in range(2, phi) if gcd(x, phi) == 1])

    # Calculate d such that (d * e) % phi = 1
    d = pow(e, -1, phi)
    return {"public_key": (e, n), "private_key": (d, n)}

# Generate and display RSA keys
keys = generate_rsa_keys()
print("RSA Keys:")
print(f"Public Key: {keys['public_key']}")
print(f"Private Key: {keys['private_key']}")

RSA Keys:
Public Key: (83431, 127697)
Private Key: (50791, 127697)

Additional notes

  1. Edge cases:

    • This function will raise an error if the input is not a positive integer greater than 1.

  2. Performance:

    • This function has a time complexity of O(√n) and a space complexity of O(1).

  3. Future improvements:

    • Potential to handle list inputs by applying the same function iteratively to each item and return a boolean list telling which numbers are prime.

    • Cache results in case repeated inputs are given.

Summary

The num_theory package offers practical and educational tools for number theory applications. From analyzing cryptographic keys to modeling real-world scenarios like savings plans, this package provides:

  • Prime factorization for understanding number properties.

  • Prime generation for problem-solving and hashing.

  • Prime checking for quick validation of numbers.

  • Arithmetic progressions for financial and mathematical modeling.

Explore the power of number theory with num_theory!