On Mar 31, 2:40 pm, Santanu Sarkar <[email protected]>
wrote:
> Is Square and Multiply algorithm to find a^x (mod N) is implemented
> in SAGE?
Hi,
If you are just interested in using Sage to find large powers mod N,
you can do the following:
sage: a=mod(5,997)
sage: a^500
972
sage: %time
a^5000000000000000000000000000000000000000000000000000000000000
CPU times: user 0.00 s, sys: 0.00 s, total: 0.00 s
Wall time: 0.00 s
966
William Stein's number theory text implies that this is done in Sage
using binary representation, which I think is very similar to what you
mean by Square and Multiply (Sage Example 2.3.15) but I suppose it is
possible that this is actually done with some more efficient variant
on this. If it calls power_mod, though, I guess it really is just
this; do
sage: power_mod??
for more details. I hope this helps.
- kcrisman
--~--~---------~--~----~------------~-------~--~----~
To post to this group, send email to [email protected]
To unsubscribe from this group, send email to
[email protected]
For more options, visit this group at
http://groups.google.com/group/sage-support
URLs: http://www.sagemath.org
-~----------~----~----~----~------~----~------~--~---
