Ayudante de factorización de Fermat

19

Nos gustaría que factorizar un semiprimo . El objetivo de este reto es encontrar dos enteros pequeños y tal que puede ser trivialmente factorized con el método de Fermat, lo que permite deducir fácilmente los factores de .u v u v N Nnortetuvtuvnortenorte

La tarea

Dado un semiprime y un entero positivo , definimos e como:k x ynortekXy

y=x2-kN

X=knorte
y=X2-knorte

Paso # 1 - Encuentrak

Primero debe encontrar el valor más pequeño posible de modo que sea ​​un número cuadrado ( también conocido como cuadrado perfecto).yky

Esto permite factorizar con una sola iteración del método de factorización de Fermat . Más concretamente, esto lleva inmediatamente a:knorte

knorte=(X+y)×(X-y)

(Actualización: esta secuencia ahora se publica como A316780 )

Paso # 2 - Factorizak

Luego debe encontrar los dos enteros positivos y manera que:vtuv

c u = x +

tuv=k
dv=x-
Ctu=X+y
rev=X-y

donde y son los factores primos de .d NCrenorte

Resumen

Su tarea es escribir un programa o función que tome como entrada e imprima o salga y en cualquier orden y en cualquier formato razonable.u vnortetuv

Ejemplo

Consideremosnorte=199163

Paso 1

El valor más pequeño posible de es , lo que da:40k40

y=28232-40×199163=7969329-7966520=2809=532kN=(2823+53)×(2823-53)kN=2876×2770

X=(40×199163)=2823
y=28232-40×199163=7969329-7966520=2809=532
knorte=(2823+53)×(2823-53)
knorte=2876×2770

Paso 2

La factorización correcta de es , porque:k = 4 × 10kk=4 4×10

k N = ( 719 × 4 ) × ( 277 × 10 ) N = 719 × 277

knorte=2876×2770
knorte=(719×4 4)×(277×10)
norte=719×277

[4 4,10][10,4 4]

Reglas

  • tuv
  • tuvnorte
  • La entrada está garantizada como semiprime.
  • Este es el código de golf, por lo que gana la respuesta más corta en bytes.
  • Las lagunas estándar están prohibidas.

Casos de prueba

N          | k    | Output
-----------+------+------------
143        | 1    | [   1,  1 ]
2519       | 19   | [   1, 19 ]
199163     | 40   | [   4, 10 ]
660713     | 1    | [   1,  1 ]
4690243    | 45   | [   9,  5 ]
11755703   | 80   | [  40,  2 ]
35021027   | 287  | [   7, 41 ]
75450611   | 429  | [ 143,  3 ]
806373439  | 176  | [   8, 22 ]
1355814601 | 561  | [  17, 33 ]
3626291857 | 77   | [   7, 11 ]
6149223463 | 255  | [  17, 15 ]
6330897721 | 3256 | [  74, 44 ]

Implementación de ejemplo

Fnortetuv

solnortetuvnorteO(1)

Arnauld
fuente
¿Estamos garantizados que la entrada Nserá de hecho un semiprime?
Greg Martin
@ GregMartin Sí, lo eres.
Arnauld

Respuestas:

8

Mathematica, 81 79 bytes

¡Gracias a Martin Ender por guardar 2 bytes!

(c=Ceiling;For[j=0;z=E,c@z>z,p=(x=c@Sqrt[j+=#])+{z=Sqrt[x^2-j],-z}];p/#~GCD~p)&

Función pura que toma un semiprime como entrada y devuelve un par ordenado de enteros positivos. El Forbucle implementa el procedimiento exacto descrito en la pregunta (usando #para la entrada en lugar de n), xtal como se define allí, aunque almacenamos en j = k*nlugar de ksí mismo y en z=Sqrt[y]lugar de ysí mismo. También calculamos p={x+z,x-z}dentro del Forciclo, que termina guardando un byte (como en el séptimo intento). Entonces los dos factores deseados son (x+z)/GCD[#,x+z]y (x-z)/GCD[#,x-z], que la expresión concisa p/#~GCD~pcalcula directamente como un par ordenado.

Curiosidades: queremos hacer un bucle hasta que zsea ​​un número entero; pero como lo vamos a usar Ceilingen el código, guarda dos bytes !IntegerQ@zpara definir c=Ceiling(lo que cuesta cuatro bytes, como saben los golfistas de Mathematica) y luego prueba si c@z>z. Tenemos que inicializar za algo, y es mejor que algo no sea un número entero para que el ciclo pueda comenzar; Afortunadamente, Ees una elección concisa.

Greg Martin
fuente
4

JavaScript (ES7), 86 81 bytes

n=>(g=k=>(y=(n*k)**.5+1|0,y+=(y*y-n*k)**.5)%1?g(k+1):n*u++%y?g(k):[--u,k/u])(u=1)

Editar: Guardado 4 bytes gracias a @Arnauld.

Neil
fuente
4

Python 2, 127 121 117 111 107 104 101 99 bytes

-1 byte gracias a Neil y -3 bytes gracias a ovs

N=input()
k=u=1;p=m=.5
while p%1:p=1+(k*N)**m//1;p+=(p*p-k*N)**m;k+=1
while N*u%p:u+=1
print~-k/u,u

Pruébalo en línea!

Curiosidades:

pse inicializa para .5que la condición del bucle sea verdadera en la primera iteración. Tenga en cuenta que es más corto almacenar p(como x+ sqrt(y)) que almacenar cada uno de ellos xy por yseparado.

adicto a las matemáticas
fuente
x*xen lugar de x**2?
Neil
@Neil Sí, por supuesto. Gracias
adicto a las matemáticas
1

Axioma, 131115 bytes

v(x)==floor(x^.5)::INT;r(n)==(k:=0;repeat(k:=k+1;x:=1+v(k*n);y:=v(x*x-k*n);x^2-y^2=k*n=>break);[w:=gcd(k,x+y),k/w])

La función que resolvería la pregunta es r (n) arriba. ungolf y prueba

vv(x)==floor(x^.5)::INT    

--(x-y)*(x+y)=k*n
rr(n)==
  k:=0
  repeat
     k:=k+1
     x:=1+vv(k*n)
     y:=vv(x*x-k*n)
     x^2-y^2=k*n=>break
  [w:=gcd(k,x+y),k/w]


(4) -> [[i,r(i)] for i in [143,2519,199163,660713,4690243,11755703]]
   (4)
   [[143,[1,1]], [2519,[1,19]], [199163,[4,10]], [660713,[1,1]],
    [4690243,[9,5]], [11755703,[40,2]]]
                                                      Type: List List Any
RosLuP
fuente