An Example

Consider n = 12007001,

note that 98153102 mod 12007001 = 626422

and 12474552 mod 12007001 = 626422,

GCD(12007001, 9815310 ? 1247455)

= GCD(12007001, 8567855) = 3001

and 12007001 = 3001 * 4001

Previous slide

Next slide

Back to first slide

View graphic version