Facebook Page
Twitter
RSS
+ Reply to Thread
Page 10 of 10 FirstFirst ... 8910
Results 91 to 97 of 97
  1. MHB Seeker
    MHB Global Moderator
    MHB Math Scholar
    MHB Coder
    I like Serena's Avatar
    Status
    Online
    Join Date
    Mar 2012
    Location
    Netherlands
    Posts
    6,910
    Thanks
    4,660 times
    Thanked
    12,850 times
    Thank/Post
    1.860
    Awards
    MHB Model Helper Award (2017)  

MHB Best Ideas (2017)  

MHB Analysis Award (2017)  

MHB Calculus Award (2017)  

MHB Model Helper Award (2016)
    #91
    Quote Originally Posted by evinda View Post
    How do we see that $q$ must divide $ord_r{(n)}$ ?
    From what came before we have that:
    $\operatorname{ord}_r n \mid r-1 = qm \tag 1$
    $\operatorname{ord}_r n > x^{1/3} \ge m \tag 2$

    Suppose that the prime $q\not\mid \operatorname{ord}_r n$.
    Then by (1) it follows that $\operatorname{ord}_r n \mid m$, doesn't it?
    Thus $\operatorname{ord}_r n \le m$, which is a contradiction with (2) isn't it?

  2. MHB Master
    MHB Site Helper
    MHB Math Helper
    evinda's Avatar
    Status
    Offline
    Join Date
    Apr 2013
    Posts
    3,310
    Thanks
    3,266 times
    Thanked
    992 times
    Awards
    MHB Model User Award (2016)  

MHB Model User Award (2014)
    #92 Thread Author
    I have also an other question. It says the following about the algorithm of post #17.





    Why are the numbers bounded by $n^2$ and not by $n$ ?

  3. MHB Seeker
    MHB Global Moderator
    MHB Math Scholar
    MHB Coder
    I like Serena's Avatar
    Status
    Online
    Join Date
    Mar 2012
    Location
    Netherlands
    Posts
    6,910
    Thanks
    4,660 times
    Thanked
    12,850 times
    Thank/Post
    1.860
    Awards
    MHB Model Helper Award (2017)  

MHB Best Ideas (2017)  

MHB Analysis Award (2017)  

MHB Calculus Award (2017)  

MHB Model Helper Award (2016)
    #93
    Quote Originally Posted by evinda View Post
    I have also an other question. It says the following about the algorithm of post #17.

    Why are the numbers bounded by $n^2$ and not by $n$ ?


    In line 6 we're calculating $n^i\bmod r$ where $r$ can be as high as $n-1$.
    With the fast exponentiation algorithm that means we need to evaluate numbers up to $(r-1)^2 = (n-2)^2$ don't we?

  4. MHB Master
    MHB Site Helper
    MHB Math Helper
    evinda's Avatar
    Status
    Offline
    Join Date
    Apr 2013
    Posts
    3,310
    Thanks
    3,266 times
    Thanked
    992 times
    Awards
    MHB Model User Award (2016)  

MHB Model User Award (2014)
    #94 Thread Author
    Quote Originally Posted by I like Serena View Post
    In line 6 we're calculating $n^i\bmod r$ where $r$ can be as high as $n-1$.
    With the fast exponentiation algorithm that means we need to evaluate numbers up to $(r-1)^2 = (n-2)^2$ don't we?
    In line 6, don't we compute at the beginning $n \mod{r}$, then at the second interation $(n \mod r) \cdot (n \mod{r})$, and so on?

  5. MHB Seeker
    MHB Global Moderator
    MHB Math Scholar
    MHB Coder
    I like Serena's Avatar
    Status
    Online
    Join Date
    Mar 2012
    Location
    Netherlands
    Posts
    6,910
    Thanks
    4,660 times
    Thanked
    12,850 times
    Thank/Post
    1.860
    Awards
    MHB Model Helper Award (2017)  

MHB Best Ideas (2017)  

MHB Analysis Award (2017)  

MHB Calculus Award (2017)  

MHB Model Helper Award (2016)
    #95
    Quote Originally Posted by evinda View Post
    In line 6, don't we compute at the beginning $n \mod{r}$, then at the second interation $(n \mod r) \cdot (n \mod{r})$, and so on?
    Yes.
    So the result of the first iteration is $n^2 \bmod r$.
    Then we calculate $(n^2 \bmod r)\cdot (n^2 \bmod r)$ don't we?
    And in one of the iterations we could have $r-1$.

    From :
    The following is an example in pseudocode based on Applied Cryptography by Bruce Schneier.[1] The inputs base, exponent, and modulus correspond to b, e, and m in the equations given above.


    As you can see, we even have an assert in there that says we need to have support up to $(r-1)^2$.

  6. MHB Master
    MHB Site Helper
    MHB Math Helper
    evinda's Avatar
    Status
    Offline
    Join Date
    Apr 2013
    Posts
    3,310
    Thanks
    3,266 times
    Thanked
    992 times
    Awards
    MHB Model User Award (2016)  

MHB Model User Award (2014)
    #96 Thread Author
    Quote Originally Posted by I like Serena View Post
    Yes.
    So the result of the first iteration is $n^2 \bmod r$.
    Then we calculate $(n^2 \bmod r)\cdot (n^2 \bmod r)$ don't we?
    And in one of the iterations we could have $r-1$.
    But then we could also need to calculate $n^5 \mod{r}$, which is equal to $n^4 \cdot n \mod{r}$.

    So why can we pick $n^2$ as an upper bound?

  7. MHB Seeker
    MHB Global Moderator
    MHB Math Scholar
    MHB Coder
    I like Serena's Avatar
    Status
    Online
    Join Date
    Mar 2012
    Location
    Netherlands
    Posts
    6,910
    Thanks
    4,660 times
    Thanked
    12,850 times
    Thank/Post
    1.860
    Awards
    MHB Model Helper Award (2017)  

MHB Best Ideas (2017)  

MHB Analysis Award (2017)  

MHB Calculus Award (2017)  

MHB Model Helper Award (2016)
    #97
    Quote Originally Posted by evinda View Post
    But then we could also need to calculate $n^5 \mod{r}$, which is equal to $n^4 \cdot n \mod{r}$.

    So why can we pick $n^2$ as an upper bound?
    In the modular_pow algorithm we calculate
    base := (base * base) mod modulus
    , where $0 \le \text{base} \le \text{modulus} -1$ each time.
    And we calculate
    result:= (result * base) mod modulus
    , where $0 \le \text{result, base} \le \text{modulus} -1$.
    So at every step the biggest product we might calculate is $(\text{modulus} -1)(\text{modulus} -1)$, after which we reduce the result to be below $\text{modulus}$.

    Suppose we have $r=17, n=19, i=10$.
    Then the algorithm is:
    \begin{array}{cccl}
    base & exponent & result & code\\
    19 & 10 & 1 & base := base \bmod 17\\
    2 & 10 & 1 & base := (base * base) \bmod 17 ; exponent := exponent >> 1 \\
    4 & 5 & 1 & result := (result * base) \bmod 17 ; exponent := exponent - 1 \\
    4 & 4 & 4 & result := (base * base) \bmod 17 ; exponent := exponent >> 1 \\
    16 & 2 & 4 & result := (base * base) \bmod 17 ; exponent := exponent >> 1 \\
    1 & 1 & 4 & (result * base) \bmod 17 ; exponent := exponent - 1 \\
    1 & 0 & 4
    \end{array}

    See how both result and base are always below $ r=17 < n=19$ (after the first step)?
    And how the base can be 16, which gets multiplied with itself?
    So $n^2$ is an upper bound.

Similar Threads

  1. Odd/even and prime
    By jasonsmith206 in forum Computer Science
    Replies: 2
    Last Post: October 19th, 2016, 17:05
  2. [SOLVED] Ratio test with an integer power of an in numerator
    By tmt in forum Calculus
    Replies: 4
    Last Post: September 7th, 2016, 00:46
  3. Prove prime test conjecture.
    By RLBrown in forum Number Theory
    Replies: 1
    Last Post: July 24th, 2016, 09:10
  4. ratio test and root test
    By aruwin in forum Calculus
    Replies: 2
    Last Post: July 19th, 2014, 04:48
  5. Prime Ideals in K[X]
    By Peter in forum Linear and Abstract Algebra
    Replies: 1
    Last Post: December 11th, 2013, 21:34

Tags for this Thread

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  
Math Help Boards