Consider 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.

gcd(a-1,b-1,c-1)= 2*m

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

run times?

Thanks,

Harsh Aggarwal