• Square roots mod p

    April 12, 2010

    The structure of Z/pZ (a.k.a. integers mod p) is simple when p-1 is not divisible by 4, that is, p=3 (4). In this case -1 is a quadratic non-residue, else there would be a subgroup of the four 4-th roots of 1, and the order of a subgroup divides the order of the group. Therefore [...]

  • Extended Euclidean in Python

    April 12, 2010

    This from Active state def egcd(a,b): # a > b > 0 ___”"” Extended great common divisor, returns x , y and gcd(a,b) so ax + by = gcd(a,b) “”" ___if a%b==0: ______return (0,1,b) ___q=[] ___while a%b != 0: ______q.append(-1*(a//b)) ______(a,b)=(b,a%b) ___(a,b,gcd)=(1,q.pop(),b) ___while q: ______(a,b)=(b,b*q.pop()+a) ___return (a,b,gcd) For information about Idle on the PC and [...]

Powered by Wordpress and MySQL. Theme by Shlomi Noach, openark.org