A198512 Half the difference between an odd squarefree semiprime's factors.

1, 2, 4, 1, 5, 7, 3, 8, 4, 10, 2, 6, 13, 3, 14, 7, 17, 9, 5, 19, 20, 6, 22, 1, 12, 13, 25, 8, 28, 29, 16, 3, 32, 11, 18, 4, 34, 19, 12, 35, 2, 21, 38, 3, 40, 6, 15, 24, 43, 17, 47, 27, 5, 18, 28, 9, 1, 20, 31, 10

Offset: 1

Author

Alonso del Arte, Oct 25 2011

Keywords

• nonn
• easy

Comments

It is trivially easy to factor small semiprimes, even with trial division. But larger semiprimes can pose quite a challenge. Behrends (2008) gives a method cryptanalysts can use to factor a large semiprime that can work reasonably well if the prime factors, even if also very large, can be figured out if they are not spaced too far apart. The method exploits the following fact about odd semiprimes:

The square of half the difference between the prime factors, when added to the semiprime, gives a perfect square. The square root of that perfect square is halfway between the two prime factors of the semiprime. For example: 39 = 3 * 13, 13 - 3 = 10, 10/2 = 5, 39 + 5^2 = 64, sqrt(64) = 8, and lastly 8 - 5 = 3 and 8 + 5 = 13.

The method then is to add perfect squares to a suspected semiprime until finding another perfect square. In turn, cryptographers should choose large semiprimes with widely distant prime factors.

Examples

			a(2) = 2 because the second odd squarefree semiprime is 21 and its two factors (3 and 7) are 4 apart, and 4/2 = 2
a(3) = 4 because the third odd squarefree semiprime is 33 and its two factors (3 and 11) are 8 apart, and 8/2 = 4
		

References

• Ehrhard Behrends, Five-Minute Mathematics, translated by David Kramer. American Mathematical Society (2008) p.s 25-26

Crossrefs

Cf. A046388.

Programs

Mathematica

(* First run the program for A046388 *) Table[(FactorInteger[A046388[[n]]][[2, 1]] - FactorInteger[A046388[[n]]][[1, 1]])/2, {n, 60}]