1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

What is the variable u in the Paillier cryptosystem?

  1. Aug 10, 2009 #1
    What is the variable "u" in the Paillier cryptosystem?

    In the Paillier cryptosystem, one of the stages during the key generation is "Ensure n divides the order of g by checking the existence of the following modular multiplicative inverse: [PLAIN]http://upload.wikimedia.org/math/4/4/6/446d6b1fcddc00432b4ce1970aa5f5ed.png*where[/URL] [Broken] function L is defined as [PLAIN]http://upload.wikimedia.org/math/d/6/7/d67db556c4ba3baeb3c281c973274e5a.png"[/URL] [Broken] (from wikipedia)
    The variable "u" is never defined though, which leads me to my question regarding what this variable is.
    The closest thing I've been able to find as an answer to this is in the original document outlining the Paillier cryptosystem where it states :
    u = 1 mod n (http://www.ippari.unict.it/~catalano/Corsi/Tesi-Cap3-Paillier.pdf Page 41), however if n>1 (which it is), "u" would always be 1 (which it cannot be according to the function "L" shown previously), and using the Extended Euclidean Algorithm the following would happen:
    u = 1 mod n
    u - 1 = qn
    u - qn= 1
    The variable "n" is known.
    Therefore "q" would be equal to 1, and "u" would equal (n+1), which would satisfy the previous relationship, however I do not think that this is correct.
    Last edited by a moderator: May 4, 2017
  2. jcsd
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Can you offer guidance or do you also need help?
Draft saved Draft deleted