Math Is Fun Forum

  Discussion about math, puzzles, games and fun.   Useful symbols: ÷ × ½ √ ∞ ≠ ≤ ≥ ≈ ⇒ ± ∈ Δ θ ∴ ∑ ∫ • π ƒ -¹ ² ³ °

You are not logged in.

#1 2009-08-16 01:36:46

Hemi08
Member
Registered: 2009-08-16
Posts: 1

Modulo Help

I am currently in university, busy with an encryption project, more specifically Elliptic Curves over prime integers.
In order to double a point on the elliptic curve, one has to use the formula:

lambda = [3*(x1)^2 + a] / 2*(y1) mod p,
where x1 and y1 is a point on the curve(x1,y1), and 'a' is part of the equation(y^2 = x^3 +a*x+b mod p), and p is the prime modulus.

Below is an example I found on the Internet for computing lambda:
Location: http://www.site.uottawa.ca/~chouinar/Handout_CSI4138_ECC_2002.pdf on page 4

Point: (3,10)
a = 1
p = 23

lambda = [3*(3)^2 + 1] / [2*10] mod 23
          = 5 / 20 mod 23
          = 0.25 mod 23
          = 6 mod 23

The problem I am having is: How do they convert the decimal result(0.25) to an integer result(6).

Another example of this can be found at: http://www.certicom.com/index.php/34-quiz-2--solutions Solution Number 5.

Your help is much appreciated.

Thank you smile

Offline

#2 2009-08-16 02:53:51

juriguen
Member
Registered: 2009-07-05
Posts: 59

Re: Modulo Help

Hi!


I think in this website they explain congruences very well http://primes.utm.edu/glossary/xpage/Congruence.html

Suppose a, b and m are any integers with m not zero, then we say a is congruent to b modulo m if m divides a-b. We write this as

    a = b (mod m).


For your example, use the transitive property: If a = b (mod m) and b = c (mod m), then a = c (mod m).

Then, lambda = 0.25 (mod 23) and 0.25 = 6 (mod 23), then lambda = 6 (mod 23). Where the second is true because 23 / (0.25 - 6) = -4


Jose


“Make everything as simple as possible, but not simpler.” -- Albert Einstein

Offline

#3 2009-08-16 09:58:05

Avon
Member
Registered: 2007-06-28
Posts: 80

Re: Modulo Help


Note that the linked document says
and not 0.25.

Since 4*6 mod 23 = 1 we have

Offline

Board footer

Powered by FluxBB