Skip to content

Instantly share code, notes, and snippets.

@pif

pif/gist:912262

Created April 10, 2011 11:19
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save pif/912262 to your computer and use it in GitHub Desktop.
Save pif/912262 to your computer and use it in GitHub Desktop.
Download ZIP
MODPOW
Raw
gistfile1.txt
http://homepages.gold.ac.uk/rachel/Mods.doc
To compute x^n mod p
Initialise y=1; u=x mod p;
Repeat
If n is odd then y:=(y*u) mod p;
n:=n div 2;
u:=(u*u) mod p;
Until n==0;
Output y;
Here the u value is the successive squaring of x, and the y value is the multiplication together of the required squared values of x.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment