Cryptography Reference
In-Depth Information
Using (9.35), (9.37), (9.38), and (9.39), we find that (9.34) equals
8
q N .
d
d
d
(9.40)
N =1
d
|
N, N/d odd
d
|
N, d odd
d
|
N, N/d even
We claim that for all N
1,
d
d
d =0 .
d
|
N, N/d odd
d
|
N, d odd
d
|
N, N/d even
Write N =2 a u with a ≥ 0and u odd. Then
d =
d 1
2 a d 1
d
|
N, N/d odd
|
u
d =
d
d
d
|
N, d odd
|
u
d =
d 2 |
d 2 .
d
|
N, N/d even
2 a− 1 u
If a = 0, the last sum is interpreted to be 0. In this case, the claim is easily
seen to be true. If a
1, then the divisors of 2 a− 1 u are of the form 2 j d 3 with
0
j
a
1and d 3 |
u . Therefore,
d 2 =
d 3
1)
d 3
(1+2+2 2 + ··· +2 a− 1 ) d 3 =(2 a
d 3 .
2 a− 1 u
d 2
|
|
u
|
u
The claim follows easily. This completes the proof of the lemma.
Since C = 0, the proof of the proposition is complete.
Example 9.3
Consider the curve
E : y 2 = x 3
58347 x + 3954150 .
We have 4 A 2 +27 B 2
372386507784192, which factors as 2 18 3 17 11, al-
though we do not need this factorization. Since 11 divides this number, we
skip 11 and start with p 1 = 13. The number of points in E ( F 13 ) is 10. The
number of points in E ( F 17 ) is also 10. Either of these facts implies that the
number of torsion points in E ( Q ) divides 10. Using the AGM, we calculate
=
ω 1 = i 0 . 156713 ...,
ω 2 =0 . 198602
···
.
This yields τ = i 0 . 78908
···
and q =0 . 0070274
···
.Wecalculate
( ω 2 / 10) = 2539 . 82553 ...,
Search WWH ::




Custom Search