123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105 |
- #!/usr/bin/ruby
- # Modular Elliptic curve arithmetic (without validation).
- # See also:
- # https://rosettacode.org/wiki/Elliptic_curve_arithmetic
- class EllipticCurveMod(x, y, N, A = 0) {
- method to_s {
- "EC Point at x=#{x}, y=#{y}"
- }
- method is_zero {
- x == 0
- }
- method neg {
- EllipticCurveMod(x, -y)
- }
- method -(EllipticCurveMod p) {
- self + -p
- }
- method +(EllipticCurveMod p) {
- if (p.is_zero) {
- return self
- }
- if (x == p.x) {
- return self*2 if (y == p.y)
- return EllipticCurveMod(0, 0, N, A)
- }
- else {
- var u = invmod(p.x - x, N) || die gcd(p.x - x, N)
- var slope = mulmod(p.y - y, u, N)
- var x2 = submod(mulmod(slope, slope, N) - x, p.x, N)
- var y2 = submod(mulmod(slope, x - x2, N), y, N)
- EllipticCurveMod(x2, y2, N, A)
- }
- }
- method *((0)) {
- EllipticCurveMod(0, 0, N, A)
- }
- method *((1)) {
- self
- }
- method *((2)) {
- var l = divmod(3*mulmod(x, x, N) + A, 2*y, N)
- var x2 = submod(mulmod(l, l, N), 2*x, N)
- var y2 = submod(mulmod(l, x - x2, N), y, N)
- EllipticCurveMod(x2, y2, N, A)
- }
- method *(Number n) {
- 2*(self * (n>>1)) + self*(n % 2)
- }
- }
- class Number {
- method +(EllipticCurveMod p) {
- p + self
- }
- method -(EllipticCurveMod p) {
- -p + self
- }
- method *(EllipticCurveMod p) {
- p * self
- }
- }
- func elliptic_curve_factorization(N, alimit = 100, B = 10000) {
- for a in (-alimit .. alimit) {
- say "Testing: #{a}"
- var curve = EllipticCurveMod(0, 1, N, a)
- B.each_prime {|p|
- var pp = p**B.ilog(p)
- try {
- curve *= pp
- }
- catch { |v|
- if (v =~ /^(\d+)/) {|m|
- return Num(m[0])
- }
- }
- }
- }
- return 1
- }
- say ("Found factor: ", elliptic_curve_factorization(14304849576137459)) #=> 16100431
- say ("Found factor: ", elliptic_curve_factorization(314159265358979323)) #=> 990371647
- #say ("Found factor: ", elliptic_curve_factorization(2**64 + 1)) # takes ~2 seconds
- #say ("Found factor: ", elliptic_curve_factorization(2**128 + 1)) # takes ~1 minute
|