Last active
May 10, 2019 00:29
-
-
Save Fiona-J-W/4630d2c6433eac4c4d62d611c8463df1 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| # from https://stackoverflow.com/questions/15390807/integer-square-root-in-python | |
| def isqrt(n): | |
| x = n | |
| y = (x + 1) // 2 | |
| while y < x: | |
| x = y | |
| y = (x + n // x) // 2 | |
| return x | |
| # everything from here on is a slightly modified version of https://github.com/goldcove/RSA-defacto | |
| def getnewnr(x, y, carry, num): | |
| """Calcualtes the next numbers""" | |
| y-=2 #Only odd numbers can be prime, subtract 2. | |
| x+=(x*2+carry)//y #(2 rows + carry) over y | |
| carry=num-(x*y) | |
| return x, y, carry | |
| def initnumber(num): | |
| """Get initial value of x, y and carry""" | |
| x = isqrt(num) | |
| #We can also check for last digit 1, 3, 7 or 9 as prime number must end with one of these. | |
| if x % 2 == 0: #not odd number | |
| x+=1 | |
| y=num//x | |
| if y % 2 == 0: #not odd number | |
| y-=1 | |
| carry=num-x*y | |
| return x,y,carry | |
| def new_factor(num): | |
| iterations=1 | |
| x,y,carry = initnumber(num) | |
| while carry != 0: | |
| iterations+=1 | |
| x, y, carry = getnewnr(x,y,carry,num) | |
| return x, y, iterations | |
| print(new_factor(3119712991*2274712361)) | |
| # output = (3119712991, 2274712361, 194601937) | |
| # => 194601937 iterations |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| from functools import reduce | |
| # from https://stackoverflow.com/questions/15390807/integer-square-root-in-python | |
| def isqrt(n): | |
| x = n | |
| y = (x + 1) // 2 | |
| while y < x: | |
| x = y | |
| y = (x + n // x) // 2 | |
| return x | |
| def comp_wheel(primes): | |
| product = reduce(lambda x,y: x*y, primes) | |
| wheel = [1] * product | |
| for p in primes: | |
| for i in range(0, product // p): | |
| wheel[p*i] = 0 | |
| offsets = [] | |
| for i in range(product): | |
| if wheel[i] == 1: | |
| offsets += [i] | |
| return product, list(reversed(offsets)) | |
| def naive_factor(n, primes = [2,3,5,7]): | |
| wheel_size, wheel = comp_wheel(primes) | |
| for p in primes: | |
| if n % p == 0: | |
| return p, 0 | |
| x = isqrt(n) | |
| y = x // wheel_size | |
| iterations = 0 | |
| for base in range(y * wheel_size, -wheel_size, -wheel_size): | |
| for offset in wheel: | |
| iterations += 1 | |
| tmp = base + offset | |
| #print(f"{base} + {offset} = {tmp} => {tmp % n}") | |
| if n % (base + offset) == 0 and tmp < n: | |
| return base + offset, iterations | |
| print(naive_factor(3119712991*2274712361, [2,3,5,7,11,13])) | |
| # output = (2274712361, 74655377) | |
| # => 74655377 iterations |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment