Wayside Health Associates Patient ID Encryptor

3 Initials (last, last, first):

Date of Birth:

- OR -

DOB (mm/dd/yyyy):

Encrypted ID:

Decrypt check:

Decryption ID:

Decrypted ID:

Legendre Symbol

Integer, a:

Odd prime, p:

Base:

Exponent:

Modulus:

Result:

Modular inverse:

Miller-Rabin Primality Test

Test:

Prime 1: Prime 2:

Modulus:
Key bit length:

Key 1:

Key 2:

Encrypt this:
Encrypts to:
Decrypts to:

Miller-Rabin Primality Test

Let p be an odd prime.
For any x where x² ≡ 1 (mod p):
[1] (x² - 1) ≡ 0 (mod p)
[2] (x + 1) · (x - 1) ≡ ±0 (mod p)
[3] x ≡ ±1 (mod p)

Fermat's Little Theorem states:
[4] x^p-1 ≡ 1 (mod p) for p prime.

Represent p by 2^k· m - 1 where m is odd
[5] Then p-1 = 2^k· m

Choose any a where 1 ≤ a ≤ p.
Substituting [5] into [4]:
[6] a^{2^k· m} ≡ 1 (mod p)
[7] a^{(2^k-1· m)²} ≡ 1 (mod p)
From [3]:
[8] a^{2^k-1m} ≡ ±1 (mod p)
If a^{2^k-1m} ≢ -1 (mod p) then a^{2^k-1m} ≡ +1 (mod p)
Repeating [6] through [8], replacing: 2^k with 2^k-1:
If a^{2^k-2m} ≢ -1 (mod p) then a^{2^k-2m} ≡ +1 (mod p)

Proceeding by induction, if each of a^{2^km}, a^{2^k-1m}, a^{2^k-2m}, ... a^2m ≢ -1 (mod p) then a^m ≡ ±1 (mod p)

Therefore, either:
[i] a^m ≡ 1 (mod p) or [ii] one of a^m, a^2m, ... , a^{2^k-1m} ≡ -1 (mod p)

To test if a given odd number, n is prime:

[A] Represent n-1 as 2^k · m
[B] Choose a₁ such that 1 < a₁ < n
[C] Calculate a^2⁰m, a^2¹m, ... , a^{2^k-1m} (mod n) for 0 ... k-1.
[D] If neither [i] or [ii] is true for any 0 ... k-1, then n is composite. a is a witness
[E] If either [i] or [ii] is true, this is a necessary (but not sufficient) condition for n being prime.
[F] Repeat [B] through [E] for independent a, a₂ through a_j
The probability that n is prime is given by 1 - (0.25)^j, where j is the count of a that have been tested.