Page 1 of 1
No full ACK in SEPT
Posted: Fri Dec 30, 2011 8:14 am
by dangermouse
My solution was very bad, in the sense that I learn little about modulo arithmetic...
I just looked for fix points in range 0..7^7 which fullfilled the following equation:
(n = 2^n mod 7^7)
and found two points. One minus 3 was the solution...
The other fixpoint is 6254451_7.
The fixpoint property is required by the ACK solution, but I do not know how to determine the correct fixpoint, if I would have received 10000 of them instead of two.
So, I would be very interested in the official way on how to solve it.
Re: No full ACK in SEPT
Posted: Wed Feb 08, 2012 7:08 pm
by MatRush
dangermouse wrote:My solution was very bad, in the sense that I learn little about modulo arithmetic...
I just looked for fix points in range 0..7^7 which fullfilled the following equation:
(n = 2^n mod 7^7)
and found two points. One minus 3 was the solution...
The other fixpoint is 6254451_7.
The fixpoint property is required by the ACK solution, but I do not know how to determine the correct fixpoint, if I would have received 10000 of them instead of two.
So, I would be very interested in the official way on how to solve it.
I think this one may be need some number theory knowledge about euler function and euler's theorem and the Knuth's up-arrow notation, In fact, when a the n and m are bigger than 4, ack(n, m) % MOD is a constant.
Posted: Wed Oct 31, 2012 7:32 pm
by Redford
Hi!
ack(7,7) = 2^2^2^2^2.... -3 (many many twos)
You have to calc
2^2^2^2^2.... -3 mod 7^7
Using Euler's theorem
http://en.wikipedia.org/wiki/Euler%27s_theorem (
a^phi(m) mod m = 1 when
a and
m are coprime) you can simplify this expression to:
2^(2^2^2^2.... mod phi(7^7)) mod 7^7, and now, the only problem is to calculate
2^2^2^2.... mod phi(7^7) = 2^2^2^2.... mod 2*3*7^6.
It's a bit harder, because "
2^2^2^2...." and modulo (
2*3*7^6) are not coprime. You can solve this using Chinese remainder theorem
http://en.wikipedia.org/wiki/Chinese_remainder_theorem.
You can divide modulo into
2 and
3*7^6, calculate
2^2^2^2.... mod 2 (it's 0) and
2^2^2^2.... mod 3*7^6, and then construct the result (because
2 and
3*7^6 are coprime, you can use Chinese remainder theorem).
But now we still have something to solve:
2^2^2^2.... mod 3*7^6. Looks very similar to previous problem (recursion
). I've created function which takes modulo (as powers of 2,3 and 7) and returns 2^2^2^2^2.... mod argument.
I hope you've understood something, writing math symbols in plaintext is quite hard and ugly
Posted: Fri Nov 02, 2012 8:47 am
by dangermouse
Thx Redford for the clear explanation
I put in my records for future reference...
Posted: Tue Apr 22, 2014 7:43 am
by Hippo
I used the same trick as for the decadic case ...
2^2^2^... modular exponentation using \phi (3^i*7^j) (i in {0,1}, j in {0,1,2,3,4,5,6,7} always leads to requirement of % 12*7^(j-1)) knowledge reaching 0 quickly ... so I have waited till 2^x % (12*7^7) stabilises.
Code: Select all
public static void main(String args[]) {
BigInteger t=BigInteger.ZERO;
BigInteger m = new BigInteger("7").pow(7);
BigInteger bm = m.multiply(new BigInteger("12"));
for(int i=0;i<20;i++) {
t=new BigInteger("2").modPow(t,bm);
System.out.printf("\n"+t.toString(7)+"("+t.mod(m).subtract(new BigInteger("3")).toString(7)+")");
}
}
Posted: Wed May 26, 2021 11:20 pm
by niteria
I had a basic plan of attack with Euler Totient function and Chinese Remainder Theorem, but I was too lazy to code it, so I eventually found
https://github.com/sasdf/ctf/tree/06ef8 ... v/bigmaffs.