charmichael-number-factorization

Quick (self) note on charmichael number factorization :

For each prime base (2,3,5,7,11…) try checking the remainder for the exponents under [(n-1)/2],[(n-1)/4],[(n-1)/8]…and so on. Once a number other than 1 is found then try :

gcd (x-1,n)

or

gcd (x+1,n).

It should result in one of the factors!

For example :

Moduluo : n=561
base : a=2

[a^(n-1/1)] mod (n) : (2^560) mod (561) = 1
[a^(n-1/2)] mod (n) : (2^280) mod (561) = 1
[a^(n-1/4)] mod (n) : (2^140) mod (561) = 67

gcd(561,68)=17

gcd(561,66)=33

561/33=17

561=3*11*17 !!

Related links :
http://mathforum.org/kb/message.jspa?messageID=5488111
https://en.wikipedia.org/wiki/Carmichael_number

Advertisements