İkili Kuadratik Formlar İle Çarpanlara Ayırma (Factorization with Binary Quadratic Forms)

Abstract

TR

Bu makalede diskriminantı pozitif olan ikili kuadratik formlar incelenmiştir. Özellikle diskriminantı iki asal sayının çarpımı olan sınıf grubunun etkisiz elemanına ait çevrimin ilginç özellikler taşıdığı gözlemlenmiştir. Bu özelliklerden yararlanarak bir çarpanlara ayırma algoritması tasarlanmış ve özellikle RSA açık anahtarlı şifreleme sisteminin anahtarlarını kırmada etkili olabileceği gösterilmiştir.

EN

In this work we investigated binary quadratic forms that have positive discriminant. Binary quadratic forms of the same discriminant have a equivalence relation among them and this equivalence relationship construct a cycle structure. There exist interesting characteristic specification in the cycle belonging identity element of class group whose the discriminant has just two factors. We designed a factorization algorithm using these features. We show that this method can be effective for breaking the keys of the public key cryptosystem RSA.

Keywords

• binary quadratic forms,integer factorization

References

1. D. Boneh, Twenty Years of Attacks on the RSA Cryptosystem, Notices of AMS, 1999.
2. D. A. Buell, Binary Quadratic Froms (Classical Theory and Modern Computations), Springer-Verlag, 1989.
3. 3. H. Cohen, A Course in Computational Algebraic Number Theory, Springer-Verlag, 2000.
4. 4. H. Cohen, H. W. Lenstra , Heuristics on class groups of number fields, Number Theory,Noordwijkerhout 1983, LN in Math. 1068, Springer-Verlag, 1984, 33-62.
5. 5. D. A. Cox, “Primes of the form x 2 + ny 2 - Fermat, class field theory, and complex multiplication,” John Wiley & Sons, New York, 1989.
6. 6. R. Crandall, C. Pomerance, Prime numbers: a computational perspective, Springer, New York, 2001.
7. 7. H. Davenport, H. Heilbronn, On the Density of Discriminants of Cubic Fields II, Proc. lloy.Soc. Lond. A 322 (1971), 405-420.
8. 8. G. Degert, Uber die bestimmung der grundeinheit gewisser reell-quadratischen zahlkorper. Abh. Math. Sem. Univ. Hamburg, 22 (1958), 92-97.

9. 9. D. Goldfeld, Gauss’ class number problem for imaginary quadratic fields, Bulletin of the AMS,Volume 13, November 1,23-37, 1985.
10. 10. P. Hartung, Proof of the existence of infinitely many imaginary quadratic fields whose class number is not divisible by 3. J. Number Theory 6 (1974), 76-278.
11. 11. H. W. Lenstra, Jr., Factoring integers with elliptic curves, Ann. of Math. 126 (1987), 649–673.
12. 12. C. Richaud, Sur la resolution des equations x 2 − Ay 2 = ±1. Atti. Acad. Pontif. Nuovi Lincei (1866), 177-182.
13. 13. R. L. Rivest, A. Shamir, L. Adleman, A method for obtaining digital signatures and public key cryptosystems. Commun. of the ACM, 21:120-126, 1978.
14. 14. D. Shanks, Class number, a theory of factorization, and genera, Proc. Symp. in Pure Maths. 20, A.M.S., Providence, R.I., 1969, 415-440.
15. 15. D. Shanks, On Gauss and composition I and II, Number Theory and Applications, R. Mollin (ed.), Kluwer Academic Publishers, 1989, 263-204.
16. 16. L.C. Washington, Introduction to Cyclotomic Fields, 2nd edition, Springer, 1996.