mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2007-05-28, 08:49   #1
ColdFury
 
ColdFury's Avatar
 
Aug 2002

26·5 Posts
Default Pseudo-random maps over an elliptic curve

Anyone have any idea how exactly pseudo-random the map F(P) = 2P behaves where P is a point on a Koblitz elliptic curve defined over GF(2^131)?

I'm currently implementing a core used for a pollard-rho attack on ecc2k-130. I know the mapping function used by pollard-rho should behave randomly as possible, and most implementations partition the points and perform a different operation depending on where the input point lies.

However, I can parallelize the core much easier if I use just the fixed function F(P) = 2P (actually any fixed function will work). So, I'm wondering, how far from random would this function actually behave? I'm not sure if the (possibly) additional distinguished points needed to be found would outweigh the faster core. I'm most worried about the repeated point doubling causing trivial cycles, but I can always have the core start from a new point at regular intervals, mitigitating this effect somewhat.

(If I use a single fixed random map, then I can easily use bit-slicing and a normal basis to do 32 point operations in parallel).
ColdFury is offline   Reply With Quote
Old 2007-05-28, 13:22   #2
R.D. Silverman
 
R.D. Silverman's Avatar
 
"Bob Silverman"
Nov 2003
North of Boston

750810 Posts
Default

Quote:
Originally Posted by ColdFury View Post
Anyone have any idea how exactly pseudo-random the map F(P) = 2P behaves where P is a point on a Koblitz elliptic curve defined over GF(2^131)?

It will depend on whether 2 is co-prime to the group order.
R.D. Silverman is offline   Reply With Quote
Old 2007-05-28, 16:25   #3
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

2,467 Posts
Default

The first couple of doublings will send you into the subgroup of <P> with all the 2's in the order removed. Further doublings will simply hop around that subgroup and will cyclically generate most (or even all? Hmm...) points there. Since the order of <P> is probably not divisible by a large power of 2, the subgroup will be large as well (almost as large as <P>) so finding a cycle takes O(N) iterations instead of the O(sqrt(N)) you wanted. Frequent re-seeding may help, but it's better to choose a proper random map instead.

Alex
akruppa is offline   Reply With Quote
Old 2007-05-28, 18:04   #4
ColdFury
 
ColdFury's Avatar
 
Aug 2002

5008 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
It will depend on whether 2 is co-prime to the group order.
The starting point has order 680564733841876926932320129493409985129, and the order of the entire curve is 4*680564733841876926932320129493409985129, so I don't believe that should not be a problem.
ColdFury is offline   Reply With Quote
Old 2007-05-29, 21:30   #5
ColdFury
 
ColdFury's Avatar
 
Aug 2002

5008 Posts
Default

I've decided to use a set of 8 (possibly 16) different point additions as the map (with no doubling).
ColdFury is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Elliptic curve arithmetic burrobert GMP-ECM 6 2012-11-08 13:05
Elliptic Curve Arithmetic Raman Math 8 2009-04-13 19:20
Elliptic curve method Dirac Factoring 11 2007-11-01 14:01
Linear recurrence on elliptic curve Unregistered Information & Answers 2 2007-01-18 17:13
Elliptic factoring with points *NOT* on the curve bongomongo Factoring 5 2006-12-21 18:19

All times are UTC. The time now is 02:52.


Sat Feb 4 02:52:13 UTC 2023 up 170 days, 20 mins, 1 user, load averages: 0.80, 0.83, 0.90

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2023, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔