Factor the Modulus

Try Small Divisors

Trial rows show which small divisors do not split the modulus.

highlighted = computed this step

Try divisors in order

The table tries small divisors in a fixed order and records the remainder each time.

first trial=2\text{first trial}=2
Try small divisorsTrial division rows are recomputed from the public toy RSA modulus.Try small divisors - n=55 factors to 5 x 11trialn mod trialdividesquotientstatus21no-no31no-no43no-no50yes11factor

Two does not divide

Trial 2 leaves remainder 1, so it is not a factor.

55 mod 2=155\bmod{}2=1
Try small divisorsTrial division rows are recomputed from the public toy RSA modulus.Try small divisors - n=55 factors to 5 x 11trialn mod trialdividesquotientstatus21no-no31no-no43no-no50yes11factor

Four is checked deterministically

The table also shows trial 4, which leaves remainder 3.

55 mod 4=355\bmod{}4=3
Try small divisorsTrial division rows are recomputed from the public toy RSA modulus.Try small divisors - n=55 factors to 5 x 11trialn mod trialdividesquotientstatus21no-no31no-no43no-no50yes11factor

Summary

A no row means the remainder is not zero. The first yes row gives a factor.

no rows before factor=3\text{no rows before factor}=3
Try small divisorsTrial division rows are recomputed from the public toy RSA modulus.Try small divisors - n=55 factors to 5 x 11trialn mod trialdividesquotientstatus21no-no31no-no43no-no50yes11factor