Método p+1-Williams

$p+1$ El método de Williams es un método para factorizar números usando secuencias de números de Lucas , desarrollado por Hugh Williams en 1982. El algoritmo encuentra un divisor primo del número . Similar al método de Pollard , pero utiliza la factorización de un número . Tiene buenos indicadores de rendimiento solo en el caso de que sea fácil de factorizar. Por regla general, no suele implementarse en la práctica debido al bajo porcentaje de tales casos [1] . $N\en \mathbb {N}$ $pags$ $norte$ $p-1$ $p+1$ $p+1$

Secuencias numéricas de Lucas

Para más cálculos, necesitamos introducir secuencias de números de Lucas y enumerar algunas de sus propiedades.

Sean y sean números enteros fijos. Las secuencias de números de Lucas se definen como [1] : $PAGS$ $q$

U_{0}(P,Q)=0,\quad U_{1}(P,Q)=1,\quad U_{n+2}(P,Q)=P\cdot U_{n+ 1 }(P,Q)-Q\cdot U_{n}(P,Q),n\geq 0

V_{0}(P,Q)=2,\quad V_{1}(P,Q)=P,\quad V_{n+2}(P,Q)=P\cdot V_{n+ 1 }(P,Q)-Q\cdot V_{n}(P,Q),n\geq 0

Deja también $\Delta =P^{2}-4Q.$

Las secuencias tienen las siguientes propiedades:

\left\{{\begin{matriz}U_{2n}=V_{n}\cdot U_{n},\\V_{2n}=V_{n}^{2}-2Q_{n}^ {2}\end{matriz}}\right.\quad (1)

\left\{{\begin{matriz}U_{2n-1}=U_{n}^{2}-Q\cdot U_{n-1}^{2},\\V_{2n-1 }=V_{n}\cdot V_{n-1}-P\cdot Q^{n-1}\end{matriz}}\right.\quad (2)

\left\{{\begin{matriz}\Delta U_{n}=P\cdot V_{n}-2Q\cdot V_{n-1},\\V_{n}=P\cdot U_{ n}-2Q\cdot U_{n-1}\end{matriz}}\right.\quad (3)

\left\{{\begin{matriz}U_{n+m}=U_{m}\cdot U_{n+1}-Q\cdot U_{m-1}\cdot U_{n},\ \\Delta U_{n+m}=V_{m}\cdot V_{n+1}-Q\cdot V_{m-1}\cdot V_{n}\end{matriz}}\right.\quad ( cuatro)

\left\{{\begin{matriz}U_{n}(V_{k}(P,Q),Q^{k})=U_{nk}(P,Q)/U_{k}( P,Q),\\V_{n}(V_{k}(P,Q),Q^{k})=V_{nk}(P,Q)\end{matriz}}\right.\quad ( 5)

Para probar estas propiedades, considere las fórmulas explícitas para la secuencia de números de Lucas :

U_{n}(P,Q)={\frac {\alpha ^{n}-\beta ^{n)){\alpha -\beta ))

V_{n}(P,Q)=\alpha ^{n}+\beta ^{n},

donde y son las raíces del polinomio característico $\alfa$ $\beta$

x^{2}-P\cdot x+Q

Usando fórmulas explícitas y el teorema de Viette :

P=\alpha +\beta ;\quad Q=\alpha \cdot \beta ,

obtenemos expresiones y ${\ estilo de visualización (1), (2), (3), (4)}$ ${\ estilo de visualización (5).}$

A continuación, destacamos una propiedad más:

Si GCD y luego: y de donde ${\ estilo de visualización (N, Q) = 1 \ cuádruple}$ $P^{\prime }Q\equiv P^{2}-2Q\mod N,\quad$ $P^{\prime }\equiv \alpha /\beta +\beta /\alpha \quad$ $Q^{\prime }\equiv 1,\quad$

U_{2m}(P,Q)\equiv P\cdot Q^{m-1}\cdot U_{m}(P^{\prime },1)\mod N\quad (6)

Y finalmente formulamos el teorema:

Si p es un número primo impar y el símbolo de Legendre es , entonces:

p\mid Q

{\ estilo de visualización \ épsilon = (\ Delta / p)}

\left\{{\begin{matriz}U_{(p-\epsilon )m}(P,Q)\equiv 0\mod p,\\V_{(p-\epsilon )m}(P, Q)\equiv 2Q^{m(1-\epsilon)/2}\mod p\end{matriz}}\right.\quad (T1)

La demostración de este teorema es laboriosa y se encuentra en el libro de D. G. Lemer [2] .

El primer paso del algoritmo

Sea un divisor primo de un número factorizable , y se realiza la expansión: $pags$ $norte$

p+1=\prod _{i=1}^{k}q_{i}^{\alpha _{i)),

donde están los números primos. $q_{yo}$

Dejar $B=\max\{q_{i}^{\alpha _{i}}|\forall i:1\leq i\leq k\}.$

Introduzcamos un número donde los grados se escojan de tal forma que $R=\prod_{i=1}^{k}q_{i}^{\beta_{i)),$ $\beta _{i}$ $q_{i}^{\beta _{i}}\leq B,q_{i}^{\beta _{i}+1}>B\quad \forall i:1\leq i\leq k .$

entonces [1] ${\ estilo de visualización p + 1 | R.}$

Además, según el teorema, si mcd entonces ${\ estilo de visualización (T1),}$ ${\ estilo de visualización (N, Q) = 1, (\ Delta / p) = -1,}$ $p|U_{R}(P,Q).$

Y, por lo tanto, se encuentra MCD , es decir, el divisor del número buscado [1] . ${\ estilo de visualización pag|}$ ${\ estilo de visualización (U_ {R} (P, Q), N),}$ $norte$

Vale la pena señalar que los números no se conocen en la etapa inicial del problema. Por lo tanto, para simplificar la tarea, haremos lo siguiente: ya que por la propiedad (2) A continuación, usamos la propiedad (6) y obtenemos: ${\ estilo de visualización P, Q, p}$ $p|U_{R}(P,Q),$ $p|U_{2R}(P,Q).$ $p|U_{R}(P^{\prime },1).$

Así, sin pérdida de generalidad, podemos afirmar que [1] ${\ estilo de visualización Q = 1.}$

A continuación, usamos el teorema del cual concluimos que ${\ estilo de visualización (T1),}$

V_{(p-\epsilon)m}(P,1)\equiv 2\mod p;

y por lo tanto [1] $p|(V_{R}(P,1)-2).$

Ahora elige algún número tal que mcd $PAGS$ ${\ estilo de visualización (P ^ {2} -4, N) = 1;}$

Designamos:

V_{n}(P)=V_{n}(P,1),\quad U_{n}(P)=U_{n}(P,1).

Finalmente, necesitas encontrar GCD [1] ${\ estilo de visualización (V_ {R} (P) -2, N).}$

Para buscar , proceda de la siguiente manera [1] : ${\ Displaystyle V_ {R} (P)}$

1) descomponer en forma binaria: donde . $R$ $R=\sum_{i=0}^{t}b_{i}2^{ti},$ ${\ estilo de visualización b_ {i} = 0,1}$

2) introducimos una secuencia de números naturales . Al mismo tiempo ; ${\displaystyle \{f_{n}\}:f_{0}=1;f_{k+1}=2f_{k}+b_{k+1))$ ${\ estilo de visualización f_ {t} = R}$

3) buscamos pares de valores según la siguiente regla: ${\ estilo de visualización (V_{f_{k+1)),V_{f_{k+1}-1})}$

(V_{f_{k+1)),V_{f_{k+1}-1})=\left\{{\begin{matriz}(V_{2f_{k)),V_{2f_{ k}-1}), cuando \ cuádruple b_{k+1}=0;\\(V_{2f_{k}+1},V_{2f_{k}}), cuando\cuádruple b_{k+1} =1\end{matriz}}\right.

donde

V_{0}(P)=2,V_{1}(P)=P

4) los valores se buscan de acuerdo con las reglas (que se derivan de las propiedades y la definición de la secuencia de números de Lucas ): $V_{2f_{k}-1},V_{2f_{k)),V_{2f_{k}+1}$ $(1), (2)$

\left\{{\begin{matriz}V_{2f-1}\equiv V_{f}V{f-1}-P\mod N;\\V_{2f}\equiv V_{f}^ {2}-2\mod N;\\V_{2f+1}\equiv PV_{f}^{2}-V_{f}V_{f-1}-P\mod N\end{matriz}}\ Correcto.

Para valores predeterminados, es decir, obtenemos el resultado: ${\ estilo de visualización N = 451889, R = 2520, P = 6}$

374468

Comprobemos este valor. Para ello, consideramos GCD GCD y . ${\ estilo de visualización (V_ {R} (P) -2, N) =}$ ${\ estilo de visualización (374468-2.451889) = 139}$ $\quad 451889\vdots 139$

Si elegimos números sin éxito en el primer paso , es decir, resultó que GCD , entonces debemos continuar con el segundo paso. De lo contrario, el trabajo se completa [1] . ${\ estilo de visualización R, P}$ ${\ estilo de visualización (V_ {R} (P) -2, N) = 1}$

El segundo paso del algoritmo

Que el número tenga algún divisor primo mayor que pero menor que algún , es decir: $p+1$ $s$ $B$ $B_{2}$

p=s\cdot (\prod_{i=1}^{k}q_{i}^{\alpha_{i)))-1

, dónde

{\displaystyle B<s\leq B_{2))

Introduzca una secuencia de números primos . ${\displaystyle \{s_{j}:B<s_{j}\leq B_{2}\quad \forall j=1,2,...,k\))$

Introducimos otra secuencia: ${\displaystyle \{d_{j}:2d_{j}=s_{j+1}-s_{j}\quad \forall j=1,2,...,k-1\))$

A continuación, definimos:

T[s_{i}]\equiv \Delta U_{s_{i}R}(P)/U_{R}(P)\mod N

Usando la propiedad , obtenemos los primeros elementos: ${\ estilo de visualización (5)}$

\left\{{\begin{matriz}T[s_{1}]\equiv PV[s_{1}]-2V[s_{1}-1]\mod N;\\T[s_{1 }-1]\equiv 2V[s_{1}]-PV[s_{1}-1]\mod N\end{matriz}}\right.

A continuación, usamos la propiedad y obtenemos: $(cuatro)$

\left\{{\begin{matriz}T[s_{i+1}]\equiv T[s_{i}]U[2d_{i}+1]-T[s_{i}-1] U[2d_{i}]\mod N,\\T[s_{i+1}-1]\equiv T[s_{i}]U[2d_{i}]-T[s_{i}-1] U[2d_{i}-1]\mod N\end{matriz}}\right.

Así calculamos $T[s_{i}],\forall i=1,2,\ldots,k$

A continuación, consideramos:

H_{t}=

MCD para

(\prod_{i=1}^{t}T[s_{i}],N)

t=1,2,\ldots,k

Tan pronto como obtenemos , detenemos los cálculos [1] . $H_{t}\neq 1$

Para valores predeterminados, es decir, obtenemos el resultado: ${\ estilo de visualización N = 451889, B = 10, B_ {2} = 50, P = 7}$

139,

Cuál es la respuesta correcta.

Comparación de velocidad

El autor de este método realizó pruebas y métodos en la máquina AMDAHL 470-V7 en 497 números diferentes, lo que mostró que, en promedio, el primer paso del algoritmo es aproximadamente 2 veces más lento que el primer paso del algoritmo , y el segundo el paso es unas 4 veces más lento [1] . $p-1$ $p+1$ $p+1$ $p-1$

Aplicación

Debido al hecho de que el método de factorización es más rápido, el método - rara vez se usa en la práctica [1] . $p-1$ $p+1$

Registros

Por el momento (14 de diciembre de 2013), los tres divisores primos más grandes [3] encontrados por el método consisten en 60, 55 y 53 dígitos decimales. ${\ estilo de visualización P+1}$

Número de dígitos	pags	divisor de números	Encontrado (por quién)	Encontrado (cuando)	B	B2
60	725516237739635905037132916171116034279215026146021770250523	${\ estilo de visualización L_ {2366}}$	A. Kruppa P.Montgomery	31.10.2007	${\ estilo de visualización 10^{11}}$	$10^{15}$
55	1273305908528677655311178780176836847652381142062038547	$782\cdot 6^{782}+1$	P. Leyland	16/05/2011	$10^{{9}}$	${\ estilo de visualización 10^{13}}$
53	60120920503954047277077441080303862302926649855338567	$682\cdot 5^{682}-1$	P. Leyland	26.02.2011	${\ estilo de visualización 10^{8}}$	$10^{12}$

Aquí está el miembro 2366 de la secuencia numérica de Lucas. ${\ estilo de visualización L_ {2366}}$

Notas

↑ 1 2 3 4 5 6 7 8 9 10 11 12 Williams, 1982 .
↑ Lehmer, 1930 .
↑ Factores de registro encontrados por el método p+1 . Fecha de acceso: 13 de diciembre de 2013. Archivado desde el original el 18 de diciembre de 2013. (indefinido)

Literatura

Williams HC Un método p+1 de factorización = Un método p+1 de factorización // American Mathematical Society. - 1982. - T. 39 , núm. 159 . - S. 225-234 . — ISSN 00255718 .
D. H. Lehmer. Una teoría extendida de las funciones de Lucas (inglés) = Una teoría extendida de las funciones de Lucas // Ann. de Matemáticas.. - 1930. - V. 31 , no. 2 . - S. 419-448 .
Ishmukhametov Sh. T. Métodos de factorización de números naturales: Libro de texto . - Kazan: Universidad de Kazan, 2011. - S. 60-61. — 190 págs.

Enlaces

https://web.archive.org/web/20170222131210/http://www.mersennewiki.org/index.php/P_Plus_1_Factorization_Method