I was looking through Weregoose's posts the other day, and I noticed this obfuscated routine:
Code:
I have slightly de-obfuscated it to this:
Code:
It looks like it repeatedly calculates X²+1 modulo N, starting from 2, advancing A one step and B two steps each time, until A and B are equal modulo some divisor of N, then outputs that divisor. But I can't figure out the point of the routine. Is it some obscure number-theoretical property? Can anyone help (perhaps Weregoose himself)?
By the way, here's a table of the first few values of A and B (not modulo anything).
Code:
EDIT: The sequence is https://oeis.org/A003095, and the period in the residues modulo n is https://oeis.org/A248218. I'm still puzzled.
Code:
"int(NfPart((X²+1)/N→Y1
"gcd(N,abs(max(∆List(Ans→u
Ans→N:{2,2
Repeat u≠1
Y1({Ans(1),Y1(Ans(2:End:u
I have slightly de-obfuscated it to this:
Code:
2→A
2→B
Input N
Repeat Ans≠1
remainder(A²+1,N→A
remainder((B²+1)²+1,N→B
gcd(N,abs(A-B
End
Ans
It looks like it repeatedly calculates X²+1 modulo N, starting from 2, advancing A one step and B two steps each time, until A and B are equal modulo some divisor of N, then outputs that divisor. But I can't figure out the point of the routine. Is it some obscure number-theoretical property? Can anyone help (perhaps Weregoose himself)?
By the way, here's a table of the first few values of A and B (not modulo anything).
Code:
A B B-A
----------------------------
2 2 0
5 26 21=3×7
26 458330 458304=2^6×3×7×11×31
677 4.413e22 3^3×5^3×7×19×31×37×97×2957×298814209
458330
2.101e11
EDIT: The sequence is https://oeis.org/A003095, and the period in the residues modulo n is https://oeis.org/A248218. I'm still puzzled.
