Results 1 to 2 of 2

Math Help - Modulus Help

  1. #1
    Newbie
    Joined
    Aug 2009
    Posts
    1

    Modulus 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, 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: 3.4 QUIZ 2 ~ Solutions Solution Number 5.

    Help is much appreciated.

    Thank you
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Opalg's Avatar
    Joined
    Aug 2007
    From
    Leeds, UK
    Posts
    4,041
    Thanks
    7
    Quote Originally Posted by Hemi08 View Post
    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).
    Best not to use decimals in calculations like this. Write 5/20 as 1/4. You are working in the field of numbers mod 23, and in that field you want to find the inverse of 4 (most people would actually write it as 4^{-1}\!\!\!\pmod{23}).

    The inverse of a number is the number that you multiply it by to get 1. In a finite number field there are no fractions, just integers (reduced by the modulus). In the field of numbers mod 23, we ignore multiples of 23. So the inverse of 4 is going to be an integer x (between 1 and 22) such that 4x is equal to 1 (plus a multiple of 23). Since 46 = 24 = 1 + 23, it follows that 6 is the inverse of 4 in that number field.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Modulus
    Posted in the Algebra Forum
    Replies: 2
    Last Post: June 22nd 2011, 07:11 AM
  2. modulus
    Posted in the Algebra Forum
    Replies: 2
    Last Post: September 8th 2010, 11:43 AM
  3. modulus
    Posted in the Algebra Forum
    Replies: 2
    Last Post: June 13th 2009, 06:32 AM
  4. modulus
    Posted in the Algebra Forum
    Replies: 12
    Last Post: January 11th 2009, 04:53 AM
  5. modulus
    Posted in the Math Topics Forum
    Replies: 1
    Last Post: September 19th 2008, 09:45 AM

Search Tags


/mathhelpforum @mathhelpforum