-
Notifications
You must be signed in to change notification settings - Fork 0
/
fp_representations.h
151 lines (137 loc) · 7.97 KB
/
fp_representations.h
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
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
#ifndef FP_REPRESENTATIONS_H
#define FP_REPRESENTATIONS_H
#include "real_quadratic_orders.h"
GEN fprepinit (GEN f, GEN p, GEN b, GEN d, GEN k);
/* (f, p) representation initialization.
* Input: Real number f >= 1 (or NULL for unknown/unimportnat);
integers p, d and k;
real quadratic ideal b = [S, [Q, P]] (as output by rqiinit).
* Output: [[f, p], [b, d, k]] = [[f, p], [[S, [Q, P]], d, k]].
* (Representation is checked for validity, ideal b is not.)
*/
GEN fpremove(GEN fprep, GEN T, GEN C, GEN s);
/* Remove factor from (f, p) representations.
* Input: (f, p) representation fprep = [[f, p], [mb, d, k]] of some real quadratic ideal a;
integers T, C and s, such that
if m = |(A + B*sqrt(d))/C|, then T = 2^s*A + B*floor(2^s*sqrt(d)) and s such that 2^s*|C| > 2^(p+4)*|B|.
* Output: [[f + 9/8, p], [b, d, k]], an (f + 9/8, p) representation (b, d', k') of a.
*/
GEN numult(GEN O, GEN fprep1, GEN fprep2, long flag);
/* NUMULT: NUCOMP for (f, p) representations.
* Input: Real quadratic order O (as output by rqoinit);
Reduced (f', p) representation fprep1 = [[f', p], [b', d', k']] of invertible ideal a';
Reduced (f'', p) representation fprep2 = [[f'', p], [b'', d'', k'']] of invertible ideal a''.
* Output: [[[f, p], [b_, d, k]], [a, b]], where
(b_, d, k) is a reduced (f, p) representation of the product a = a'*a'',
where b_ = [1, [Q, P]] with (P + sqrt(d))/Q > 1, -1 < (P - sqrt(d))/Q < 0,
k <= k' + k'' + 1,
f = f* + 17/8, where f* = f' + f'' + 2^(-p)*f'*f'' and
a, b are integers such that
b_ = ((a + b*sqrt(d))/s)/(N(b')*N(b''))*b'*b''.
* Set flag = 0 to skip some tests if you are sure that your input is correct.
*/
GEN wnear(GEN O, GEN fprep, GEN w);
/* (Find) w-near (f, p) representation.
* Input: Real quadratic order O (as output by rqoinit);
reduced (f, p) representation fprep = [[f, p], [b', d', k']] of ideal a,
where b' = (Q, P) with P + floor(sqrt(d)) >= Q and 0 <= floor(sqrt(d)) - P <= Q;
positive integer w.
* Output: [[f + 9/8, p], [b, d, k]], a w-near (f + 9/8, p) representation of the ideal a.
*/
GEN ewnear(GEN O, GEN fprep, GEN w);
/* Extended wnear.
* Input: Real quadratic order O (as output by rqoinit);
reduced (f, p) representation fprep = [[f, p], [b', d, k]] of ideal a,
where b' = [1, [Q, P]] with with P + floor(sqrt(d)) >= Q and 0 <= floor(sqrt(d)) - P <= Q;
positive integer w with k < w.
* Output: [[[f + 9/8, p], [c, g, h]], [a, b]] with integers a, b, where
(c, g, h) is a w-near (f + 9/8, p) representation of the ideal a and
c = ((a + b*sqrt(d))/Q)b.
*/
GEN wmult(GEN O, GEN fprep1, GEN fprep2, GEN w, long flag);
/* w-near multiplication.
* Input: Real quadratic order O (as output by rqoinit);
Reduced w-near (f', p) representation fprep1 = [[f', p], [b', d', k']] of invertible ideal a';
Reduced w-near (f'', p) representation fprep2 = [[f'', p], [b'', d'', k'']] of invertible ideal a''.
(w-nearness is not, and in fact cannot, be checked.)
* Output: Reduced w-near (f* + 13/4, p) representation (b, d, k) of the product a = a'*a'',
where f* = f' + f'' + 2^(-p)*f'*f''.
* Set flag = 0 to skip some tests if you are sure that your input is correct.
*/
GEN iexp(GEN O, GEN fprep, GEN w, GEN n, long flag);
/* Ideal exponentiation.
* Input: Real quadratic order O (as output by rqoinit);
w-near (f', p representation) [[f', p], [b', d', k']] = fprep of invertible real quadratic ideal a;
positive integer n.
* Output: [[f, p], [b, d, k]], a w-near (f, p) representation (b, d, k) of a^n for some suitable f.
* Set flag = 0 to skip some tests if you are sure that your input is correct.
*/
GEN addxy(GEN O, GEN fprep1, GEN fprep2, GEN x, GEN y, long flag);
/* Add x(-near) y(-near).
* Input: Real quadratic order O (as output by rqoinit);
[[f', p], [a[x], d', k'], an x-near (f', p) representation (a[x], d', k') of the ideal (1),
[[f'', p], [a[y], d'', k''], an y-near (f'', p) representation (a[y], d'', k'') of the ideal (1).
* Output: [[f, p], [a[x+y], d, k], an (x+y)-near (f, p) representation (a[x+y], d, k) of (1), where
f = f' + f'' + (f'*f'')/2^p + 13/4.
* Set flag = 0 to skip some tests if you are sure that your input is correct.
*/
GEN ax(GEN O, GEN x, GEN p);
/* (Find) a[x].
* Input: Real quadratic order O (as output by rqoinit);
positive integers x and p.
* Output: [[f, p], [a[x], d, k]], where (a[x], d, k) is an (f, p) representation of the ideal (1) in O for some f \in [1, 2^p).
*/
GEN eaddxy(GEN O, GEN fprep1, GEN fprep2, GEN x, GEN y, long flag);
/* Extended addxy.
* Input: Real quadratic order O (as output by rqoinit);
[[f', p], [a[x], d', k'], an x-near (f', p) representation (a[x], d', k') of the ideal (1),
[[f'', p], [a[y], d'', k''], an y-near (f'', p) rerepsentation (a[y], d'', k'') of the ideal (1).
* Output: [[[f, p], [a[x+y], d, k]], [a, b]], where
(a[x+y], d, k) is an (x+y)-near (f, p) representation of (1) with f = f' + f'' + (f'*f'')/2^p + 13/4 and
(a, b) are integers such that
a[x+y] = ((lambda*theta'*theta'')/(N(a[x])*N(a[y])))(1), where
lambda = (a + b*sqrt(d))/s and a[x] = theta'*a, a[y] = theta''*a.
* Set flag = 0 to skip some tests if you are sure that your input is correct.
*/
GEN crax(GEN O, GEN x, GEN p, GEN m);
/* Compact representation ax.
* Input: Real quadratic order O (as output by rqoinit);
positive integers x and p (precision used for (f, p) representations),
that satisfy 2^p > 11.2x*max(16,log_2(x));
integer m.
* Output: [[f, p], [a[x], d, k]], [[[m_0, n_0], L_0], [[m_1, n_1], L_1], ..., [[m_l, n_l], L_l]],
an x-near (f, p) representation (a[x], d, k) of the ideal (1) in O, where f < 2^(p-4)
as well as integer pairs (m_i, n_i) and positive integers L_i for i = 0, 1, ..., l = floor(log_2(x)).
* When this algorithm terminates we have a[x] = (theta) for
theta = lambda_l * \prod_{i=0}^{l-1}(lambda_i/L_{i+1})^{2^(l-i)}, where lambda_i = (m_i + n_i*sqrtd(d))/s.
* If m is nonzero, then none of the L_i share any divisors with m.
*/
GEN find(GEN O, GEN fprep, GEN c);
/* Find a (f, p) representation.
* Input: Real quadratic order O (as output by rqoinit);
reduced (f, p) representation fprep = [[f, p], [b, d, k]] of ideal a,
where b = [1, [Q, P]] with (P + sqrt(d))/Q > 1 and -1 < (P - sqrt(d))/Q < 0;
real quadratic ideal c = [1, [Q', P']], that comes after b in the infrastructure (this isn't checked);
* Output: [[[f + 1/4, p], [c, g, h]], [m, n]], where
(c, g, h) is a reduced (f + 1/4, p) representation of a,
and m, n are integers such that
N(b)*c = ((m + n*sqrtd(d))/s)*b.
*/
GEN cr(GEN O, GEN b, GEN y, GEN q, GEN m);
/* (Find a) compact representation.
* Input: Real quadratic order O (as output by rqoinit);
reduced principal ideal b = [1, [Q, P]] with (P + sqrt(d))/Q > 1 and -1 < (P - sqrt(d))/Q < 0;
y, q positive rational numbers, such that
|log_2(theta) - y| < q.
where (theta) = b;
integer m.
* Output: [[f, p], [b, d, k]], [[[m_0, n_0], L_0], [[m_1, n_1], L_1], ..., [[m_l, n_l], L_l], [[m_{l+1}, n_{l+1}], L_{l+1}]].
an (f, p) representation [[f, p], [b, d, k]] of b, as well as
integers (m_i, n_i)_i, L_i, L_{i+1} for i = 0, 1, ..., l = floor(log_2(x)), such that
b = (theta) for
theta = lambda_{l+1} * \prod_{i=0}^l (lambda_i/L_{i+1})^{2^(l-i)}, where lambda_i = (m_i + n_i*sqrtd(d))/s.
* If m is nonzero, then at most L_{l+1} shares any divisors with m.
* Known bugs:
- For small y (say less than 15), this may fail, because it hits the value immediately and cannot compute relative generators that way.
*/
#endif