def shor(N):
 a = (random.randrange((N - 2)) + 2)
 if (igcd(N, a) != 1):
  print('got lucky with rand')
  return igcd(N, a)
 print('a= ', a)
 print('N= ', N)
 r = period_find(a, N)
 print('r= ', r)
 if ((r % 2) == 1):
  print('r is not even, begin again')
  shor(N)
 answer = (igcd(((a ** (r / 2)) - 1), N), igcd(((a ** (r / 2)) + 1), N))
 return answer

def shor ( N ) : a = ( random . randrange ( ( N - 2 ) ) + 2 ) if ( igcd ( N , a ) != 1 ) : print ( 'got lucky with rand' ) return igcd ( N , a ) print ( 'a= ' , a ) print ( 'N= ' , N ) r = period_find ( a , N ) print ( 'r= ' , r ) if ( ( r % 2 ) == 1 ) : print ( 'r is not even, begin again' ) shor ( N ) answer = ( igcd ( ( ( a ** ( r / 2 ) ) - 1 ) , N ) , igcd ( ( ( a ** ( r / 2 ) ) + 1 ) , N ) ) return answer
this function implements shors factoring algorithm on the integer n the algorithm starts by picking a random number (a) and seeing if it is coprime with n .