A deterministic algorithm for computing divisors in an interval. (English) Zbl 1421.11105
Susilo, Willy (ed.) et al., Information security and privacy. 23rd Australasian conference, ACISP 2018, Wollongong, NSW, Australia, July 11–13, 2018. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 10946, 3-12 (2018).
Summary: We revisit the problem of finding a nontrivial divisor of a composite integer when it has a divisor in an interval \([\alpha,\beta]\). We use Strassen’s algorithm [V. Strassen, Jahresber. Dtsch. Math.-Ver. 78, 1–8 (1976; Zbl 0361.68070)] to solve this problem. Compared with Kim-Cheon’s algorithms [M. Kim and J. H. Cheon, Math. Comput. 84, No. 291, 339-354 (2015; Zbl 1352.11104)], our method is a deterministic algorithm but with the same complexity as Kim-Cheon’s probabilistic algorithm, and our algorithm does not need to impose that the divisor is prime. In addition, we can further speed up the theoretical complexity of Kim-Cheon’s algorithms and our algorithm by a logarithmic term \(\log (\beta -\alpha)\) based on the peculiar property of polynomial arithmetic we consider.
For the entire collection see [Zbl 1392.94009].
For the entire collection see [Zbl 1392.94009].
MSC:
| 11Y05 | Factorization |
| 11Y16 | Number-theoretic algorithms; complexity |
| 68W30 | Symbolic computation and algebraic computation |
References:
| [1] | Bluestein, LI, A linear filtering approach to the computation of the discrete fourier transform, IEEE Trans. Electroacoust., 18, 451-466, 1970 · doi:10.1109/TAU.1970.1162132 |
| [2] | Bostan, A.: Algorithmique efficace pour des opérations de base en calcul formel. Ph.D. thesis (2003). École polytechnique (in English) · Zbl 1360.13003 |
| [3] | Bostan, A.; Gaudry, P.; Schost, E., Linear recurrences with polynomial coefficients and application to integer factorization and Cartier-Manin operator, SIAM J. Comput., 36, 6, 1777-1806, 2007 · Zbl 1210.11126 · doi:10.1137/S0097539704443793 |
| [4] | Chen, Y.; Nguyen, PQ; Pointcheval, D.; Johansson, T., Faster algorithms for approximate common divisors: breaking fully-homomorphic-encryption challenges over the integers, Advances in Cryptology - EUROCRYPT 2012, 502-519, 2012, Heidelberg: Springer, Heidelberg · Zbl 1297.94059 · doi:10.1007/978-3-642-29011-4_30 |
| [5] | Coppersmith, D., Small solutions to polynomial equations, and low exponent RSA vulnerabilities, J. Cryptol., 10, 4, 233-260, 1997 · Zbl 0912.11056 · doi:10.1007/s001459900030 |
| [6] | Coron, J-S; Joux, A.; Mandal, A.; Naccache, D.; Tibouchi, M.; Catalano, D.; Fazio, N.; Gennaro, R.; Nicolosi, A., Cryptanalysis of the RSA subgroup assumption from TCC 2005, Public Key Cryptography - PKC 2011, 147-155, 2011, Heidelberg: Springer, Heidelberg · Zbl 1291.94070 · doi:10.1007/978-3-642-19379-8_9 |
| [7] | Costa, E.; Harvey, D., Faster deterministic integer factorization, Math. Comput., 83, 285, 339-345, 2014 · Zbl 1285.11148 · doi:10.1090/S0025-5718-2013-02707-X |
| [8] | Fouque, P-A; Tibouchi, M.; Zapalowicz, J-C; Stam, M., Recovering private keys generated with weak PRNGs, Cryptography and Coding, 158-172, 2013, Heidelberg: Springer, Heidelberg · Zbl 1317.94106 · doi:10.1007/978-3-642-45239-0_10 |
| [9] | Howgrave-Graham, N.; Silverman, JH, Approximate integer common divisors, Cryptography and Lattices, 51-66, 2001, Heidelberg: Springer, Heidelberg · Zbl 1006.94528 · doi:10.1007/3-540-44670-2_6 |
| [10] | Kim, M.; Cheon, JH, Computing prime divisors in an interval, Math. Comp., 84, 291, 339-354, 2015 · Zbl 1352.11104 · doi:10.1090/S0025-5718-2014-02840-8 |
| [11] | Konyagin, S.; Pomerance, C.; Graham, RL; Nešetřil, J., On primes recognizable in deterministic polynomial time, The mathematics of Paul Erdős I, 1997, Heidelberg: Springer, Heidelberg · Zbl 0869.11102 |
| [12] | Pollard, JM, Monte Carlo methods for index computation (mod \(p)\), Math. Comp., 32, 143, 918-928, 1978 · Zbl 0382.10001 |
| [13] | Pollard, J. M., Theorems on factorization and primality testing, Mathematical Proceedings of the Cambridge Philosophical Society, 76, 3, 521, 1974 · Zbl 0294.10005 · doi:10.1017/S0305004100049252 |
| [14] | Strassen, V.: Einige Resultate \(\ddot{u}\) ber Berechnungskomplexit \(\ddot{a}\) t. Jber. Deutsh. Math. -Verein. 78(1), 1-8 (1976/1977) · Zbl 0361.68070 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
