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
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
|
# File 'ext/factorization/factorization.c', line 44
static VALUE
factorize_pq(VALUE self, VALUE pq_bytes)
{
Check_Type(pq_bytes, T_STRING);
long pq_len = RSTRING_LEN(pq_bytes);
unsigned char *pq_ptr = (unsigned char *)RSTRING_PTR(pq_bytes);
uint64_t n = 0;
for (long i = 0; i < pq_len; i++) {
n = (n << 8) | pq_ptr[i];
}
if (n <= 3) {
rb_raise(rb_eArgError, "Number must be > 3");
}
uint64_t p;
if (n % 2 == 0) {
p = 2;
} else {
uint64_t d = n;
for (uint64_t c = 1; c < 256; c++) {
d = pollard_rho(n, c);
if (d != n && d > 1) break;
}
if (d == n || d <= 1) {
rb_raise(rb_eRuntimeError, "No non-trivial factors found (n might be prime)");
}
p = d;
}
uint64_t q = n / p;
if (p > q) {
uint64_t tmp = p;
p = q;
q = tmp;
}
VALUE result = rb_ary_new2(2);
rb_ary_push(result, ULL2NUM(p));
rb_ary_push(result, ULL2NUM(q));
return result;
}
|