This is a script that calculates the GCD of two integers using the Euclidean algorithm.
Extended Euclidean Algorithm
The EEA computes for you the GCD of two numbers a,b written as a sum of their respective multiples.
It also returns the multiplicative inverse a^-1 of b.
Congruence Unknown Solver
This script solves for x in the equation ax ≡ c mod n. Note that it depends upon the outputs of my GCD and EEA scripts.
If a is coprime to n, then no issue. It’s fast because you just EEA and find x through multiplication of c with the result. If a is not coprime to n, then some issue appears that are solved by using the GCD of a and n. A list of solutions for x will be returned.
Input: As listed in the equation above, a,c,n in exact positions
Output: Value(s) for x
Factoring
This is a stupid stupid method that lists all factors of a number. It literally checks all the numbers smaller than itself. Mainly for my convenience.
If it’s prime, the script says it’s prime, with a exclamation mark like this!
Chinese Remainder Theorem
This script finds a ≡ x mod mn from inputs a mod m and b mod n, using the CRT.
Input: As listed in the equation above, a,c,n in exact positions
Output: Value for x
Solving 2 Congruences - Does not work!
This doesn’t seem to work but it tries to solve input: x^2 ≡ 1 mod n if you know how to make it work lmn
Modular Exponentiation of 2^n mod k.
This script computes 2^n mod k somewhat intelligently using congruences. That’s it.
Euler’s Function
This does the Euler’s Function, which finds how many integers there are that are coprime to your number but smaller than your number.
近期评论