Experimental program estimation for the quantity of prime numbers necessary for elimination of polynomial equations without integer roots
Prikladnaâ diskretnaâ matematika, no. 10 (2009), pp. 84-87
Citer cet article
Voir la notice de l'article provenant de la source Math-Net.Ru
This work deals with a way of eliminating polynomial equations in a single unknown without integer roots with their right parts' known spectrum determined by estimation based on the difference between the polynom's maximum and minimum values in a certain interval. Ideas introduced by Gauss and developed to the case of any prime numbers and any residues were used to elaborate this method. The solutions of congruence in a single variable which demonstrate the elimination method potential are also given. A program in the packet of symbolic calculations is offered for the experimental estimation of the necessary length of the prime numbers list used for equation elimination. The use of a shorter list allows to expect the algorithm's time complexity reduction when this elimination is applied.
[1] Zachesov Yu. L., Salikhov N. P., “O metode resheniya polinomialnogo sravneniya $p(x)=0\mod N$”, Obozrenie prikladnoi i promyshlennoi matematiki, 15:5 (2008), 769–784 | MR
[2] Kolchin V. F., Sevastyanov B. A., Chistyakov V. P., Sluchainye razmescheniya, Nauka, M., 1976 | MR
[3] Knut D., Iskusstvo programmirovaniya dlya EVM. T. 3. Sortirovka i poisk, Mir, M., 1978, 844 pp. | MR | Zbl