Modular Arithmatic/Number Theory Utilities

Reduces a mod n



              

Extended Euclidean Algorithm, GCD

For g=gcd(a,b) uses the Extended Euclidean Algorithm to write g=ka+mb for integers k and m with k>0.



              

RSA Decryption Key

For composite N=pq (p and q primes) and encryption exponent e with gcd(e, \(\phi\)(N))=1, finds the smallest positive decryption exponent d.



              

Modular Exponentiation

For \(b,n\in \Bbb Z\) and \(m\in\Bbb N\), finds \(b^m\) (mod n)



              

Relatively Prime Integers

Given \(n\in\Bbb Z\) finds values in list relatively prime to n.


For a given \(n\in\Bbb N\), you may find all \(0\le a<n\) with \(gcd(a,n)=1\) or only those values from a list that you enter.



              

Square Roots Modulo n

For natural number n and integer a, finds a's modulo n square roots if it has any.



              

Cyclic Subgroup by Generated by Element \(a\in(\Bbb Z/n\Bbb Z)^*\)

For integers a, n with gcd(a, n)=1, finds the cyclic subgroup \(H=<a>\) for \(a\in (\Bbb Z/n\Bbb Z)^*\).



              

Chinese Remainder Theorem

Solve simultaneous congruences using the Chinese Remainder Theorem.


For \(x\equiv c_i (mod n_i)\), first row enter \(c_i\)'s, second enter corresponding \(n_i\)'s.





              

Pollard's Algorithm

For natural number n, the algorithm attempts to factor n. It can fail to factor composities which have no relatively small prime factors and, as it involves two random selections, will not always produce the same output for a given imput.



              

Specify an elliptic curve \( E:\ y^2=x^3+Ax+B\ (mod\ p) \).



                

For points \( P, Q\in E \), find \(P\oplus Q\). Enter the point at infinity as (0,0).


Input \(P\)

Input \(Q\)