Timeline for Fastest algorithm to compute (a^(2^N))%m?
Current License: CC BY-SA 3.0
10 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Mar 22, 2012 at 23:56 | comment | added | Gerry Myerson | At a recent conference, David Moulton asked whether there is an algorithm, polynomial in $\log d$ and $\log m$, to compute $2^{2^d}\mod m$. I believe no such algorithm is known. | |
| Mar 22, 2012 at 15:53 | comment | added | Jeremy Teitelbaum | This might be helpful. Note the reference to Knuth. He discusses computing x^n mod p faster than repeated squaring by algorithms depending on n. stackoverflow.com/questions/101439/… | |
| Mar 22, 2012 at 13:33 | answer | added | Igor Rivin | timeline score: 5 | |
| Mar 22, 2012 at 10:31 | comment | added | Gerhard Paseman | I think I mean mod phi(p) instead of mod p-1 above. Gerhard "Going Back To Sleep Now" Paseman, 2012.03.22 | |
| Mar 22, 2012 at 10:27 | comment | added | Gerhard Paseman | In fact, repeated squaring of 2 mod p-1 for prime powers p dividing m could have some speed advantage for large N. Gerhard "Really Does Like Repeated Squaring" Paseman, 2012.03.22 | |
| Mar 22, 2012 at 10:21 | comment | added | Gerhard Paseman | You could start with repeated fourth powers. Gerhard "Does Like Repeated Squaring Though" Paseman, 2012.03.22 | |
| Mar 22, 2012 at 9:33 | comment | added | Steve Huntsman | It is hard to imagine beating repeated squaring. | |
| Mar 22, 2012 at 8:57 | history | edited | Vincent | CC BY-SA 3.0 |
added 67 characters in body
|
| Mar 22, 2012 at 8:02 | history | edited | user5810 | CC BY-SA 3.0 |
removed incorrect tag and fixed typo
|
| Mar 22, 2012 at 7:54 | history | asked | Vincent | CC BY-SA 3.0 |