Carol/Kynea and PRP
- View SourceConsider a number of this type n which is composite.
suppose all the factors of n are known then a*b*c=n
a,b,c>1 and the number has only 3 factors for simplicity reasons.
m in most cases will be 1 but can differ.
if this is true then 2*m also divides n-1
With that said it can be proven that there is a number h such that
h^(2*m)-1 = 0 (mod n)
h^(n-1)-1=0 (mod n)
or n is a PRP for base h.
An open question related to above:
Given x,k and a prime p solve for a
a^x= k (mod p)
How would this be done? What algorithms can be used? What are there