Skip to Content

Programming knowledge

Last modified by Alexandru Pentilescu on 2025/05/12 16:57

Contents

This page is where I will write all of my various bits of knowledge with regards to programming and software engineering techniques, as well as some math bits that are tangentially related to software development, in one way or another.

Hardware exponentiation

When doing expontiation between two integers modulus n, computer hardware optimizes this operation in a way that's not immediately obvious. Normally, one would simply multiply the base by itself by the number of times of the exponent and then do remainder division on the modulus.

However, it's important to note that this is extremely inefficient and, often times, it's also impractical since the numbers will quickly grow so large that it's difficult for the hardware to properly represent them accurately. The solution to this is the following optimization:

def a_to_the_b_mod_n(a, b, n):
 if b == 0:
   return 1
 if is_even(b):
   return a_to_the_b_mod_n((a * a) % n, b / 2, n)
 return (a * a_to_the_b_mod_n(a, b - 1, n)) % n

Generating large random prime numbers

One of the most powerful features of modern computers is their ability to generate relatively large prime numbers very quickly. To do this, they usually employ the following algorithm:

def generate_n_digits_in_length_prime(n):
  num = generate_n_digits_in_length_number(n)
 while is_prime(num) == False
    num = generate_n_digits_in_length_number(n)
    

The is_prime function should be an implementation of the Miller-Rabin test, which is the industry standard for testing the primality of large numbers.

The Miller-Rabin primality test

The Miller-Rabin primality test is an extension of the Miller primality test. Specifically it uses a relatively small number of randomly chosen odd integers that are smaller than N (where N is the number being tested for primality), usually N. If and only if all these tests pass (i.e. they claim that N is prime), then we're to assume that N is prime. The probability of a large number N passing the primality test despite not being prime, when 10 different numbers are randomly chosen to be used, is at most 0.00000095367431640625 (i.e (1/4)10).

The Miller primality test

The Miller primality test is an extension of Fermat's Little Theorem.

Specifically, it says that to test a large number N for primality, we are to follow the following steps:

  1. Choose a number a smaller than N. This number is a
  2. Compute aN
  3. Divide the result from the above step by N and check the remainder of that division (i.e. do modulus division). If the remainder is not 1 then the number is composite (i.e. not prime) and stop. If it is 1 but N is odd, it is composite. If it is 1 but N is even, continue to the next step. Keep note of the remainder of this division (i.e. the 1) for later
  4. Divide N by 2. This new number is N'
  5. Compute again aN' and then do modulus division against N. Keep note of the remainder again for later. This remainder is to be considered BEFORE in the sequence that we're keeping note of, compared to the 1 calculated in step 3.
  6. Check if N' is odd. If it is, stop. If not, repeat from step 4 onwards, with N' being the new N.

Once the algorithm above is followed, you should have a sequence of numbers that you kept note of. This sequence will determine whether N is indeed prime.

The sequence needs to end in 1. If it does not, N is composite.
Any number in the sequence before 1 has to be another 1 or N-1. If it is, N is likely prime (although there are false positives!).