/
sophie_germain_factorization_method_fast.sf
70 lines (54 loc) · 2.41 KB
/
sophie_germain_factorization_method_fast.sf
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#!/usr/bin/ruby
# Author: Trizen
# Date: 11 November 2023
# https://github.com/trizen
# A simple factorization method, based on Sophie Germain's identity:
# x^4 + 4y^4 = (x^2 + 2xy + 2y^2) * (x^2 - 2xy + 2y^2)
# This method is also effective for numbers of the form: n^4 + 4^(2k+1).
# See also:
# https://oeis.org/A227855 -- Numbers of the form x^4 + 4*y^4.
# https://www.quora.com/What-is-Sophie-Germains-Identity
func sophie_germain_decomposition(n) {
var t = n.iroot(4)
var u = (n - t**4)>>2
if (u.is_power(4)) {
var (x,y) = (t, u.iroot(4))
assert_eq(n, x**4 + 4*y**4)
return [x, y]
}
var t = (4*n).iroot(4)>>1
var u = (n - 4*t**4)
if (u.is_power(4)) {
var (x,y) = (u.iroot(4), t)
assert_eq(n, x**4 + 4*y**4)
return [x, y]
}
return []
}
func sophie_germain_factors(n) {
var arr = sophie_germain_decomposition(n) || return []
var (x,y) = arr...
var f = [x**2 - 2*x*y + 2*y**2, x**2 + 2*x*y + 2*y**2]
assert_eq(f.prod, n)
return f
}
var x = 642393874177414576297153561759
var y = 714067453700987
for n in ([(x**4 + 4*y**4), (4*x**4 + y**4)]) {
say sophie_germain_decomposition(n)
}
assert_eq(sophie_germain_decomposition(x**4 + 4*y**4), [x, y])
assert_eq(sophie_germain_decomposition(y**4 + 4*x**4), [y, x])
say sophie_germain_factors(77001290479960160497341160397504245)
say sophie_germain_factors(19250322619990040124335290452638485)
say sophie_germain_factors(27606985387162255149739023449108101809804435888681546220650096903087665)
say sophie_germain_factors(173291855882550928723650886508942731464777317210988535948154973788413831737851601439998400381508723631086950685087723242628644864)
say sophie_germain_factors(13093562431584567480052758787310396608866568184172259157933165472384535185618698219533080369303616628603546736510240284036869026183541572213318079483505)
__END__
[642393874177414576297153561759, 714067453700987]
[714067453700987, 642393874177414576297153561759]
[277491095817736105, 277491031750210669]
[138745604154213509, 138745459629795665]
[166153499473114514665395754616490745, 166153499473114453560556010453601017]
[13164036458569648337239753460497746266300898132282617629258080512, 13164036458569648337239753460419861813422875717854660184319779072]
[3618502788666131106986593281521497141767405545090156208559806116590740633113, 3618502788666131106986593281521497099061968496512379043906292883903830095385]