Garbell quadràtic

l'algoritme de garbell quadràtic (QS de l'anglés quadratic sieve), és un algoritme de factorización de sancers i, en la pràctica, el segon método més ràpit conegut (despuix de la garbell general del cos de números). És encara el més ràpit per a sancers que tenen 100 o menys dígits decimals, i és considerat molt més senzill que el garbell de cossos numèrics. És un algoritme d'factorización de propòsit general, lo que significa que el seu temps d'eixecució únicament depén el tamany del sancer a ser factorizado, i no sobre una estructura especial o propietats. Va ser inventat per Carl Pomerance en 1981 com una millora al garbell llineal de Schroeppel.^[1]

Vore també

Referències

↑ Carl Pomerance, Analysis and Comparison of Some Integer Factoring Algorithms, in Computational Methods in Number Theory, Part I, H.W. Lenstra, Jr. and R. Tijdeman, eds., Math. Centre Tract 154, Amsterdam, 1982, pp 89-139.

Richard Crandall and Carl Pomerance (2001). Prime Numbers: A Computational Perspective, 1st edició, Springer. ISBN 0-387-94777-9. Section 6.1: The quadratic sieve factorization method, pp. 227–244.

Referències

Este artícul conté una traducció derivada de «Criba cuadrática» de Wikipedia en castellà publicada baix la Llicència de documentació lliure de GNU i la Llicència Creative Commons Reconeiximent-CompartirIgual 4.0 Internacional.

[1] Carl Pomerance, Analysis and Comparison of Some Integer Factoring Algorithms, in Computational Methods in Number Theory, Part I, H.W. Lenstra, Jr. and R. Tijdeman, eds., Math. Centre Tract 154, Amsterdam, 1982, pp 89-139.

[1]