Results 1 to 4 of 4

Thread: reduction mod

  1. #1
    Junior Member
    Joined
    Jun 2008
    Posts
    39

    reduction mod

    let n=1105, so n-1=2^4(69) Compute the values of

    2^69(mod1105), 2^2*69(mod 1105), 2^4*69(mod1105), 2^8*69(mod1105),

    Use the Rabin Miller test to conclue that n is composite....

    Where do I begin and how?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    5
    Quote Originally Posted by duggaboy View Post
    let $\displaystyle n=1105,$ so $\displaystyle n-1=2^4\times 69$ Compute the values of

    $\displaystyle [2^{69} \mod 1105],\ [2^{2 \times 69} \mod 1105],\ [2^{4 \times 69}\mod 1105],\ [2^{8 \times 69} \mod 1105]$

    Use the Rabin Miller test to conclue that n is composite....

    Where do I begin and how?
    In the Rabin-Miller test for the (pseudo) primality of $\displaystyle 1105$ we have $\displaystyle s=4$ and $\displaystyle d=69$

    So $\displaystyle a$ is a witness to the primallity of $\displaystyle 1105$ if:

    $\displaystyle
    a^d \not \equiv 1 \mod 1105
    $

    and

    $\displaystyle
    a^{2^r.d} \not \equiv -1 \mod 1105; \forall \ r \in \{0,\ ..., \ s-1\}
    $

    So if you compute the values asked for and the first is not congruent to $\displaystyle \pm 1 \mod 1105$ and the others are not congruent to $\displaystyle -1 \mod 1105$, then $\displaystyle 2$ is a witness to the compositness of $\displaystyle 1105$. (In fact if the conditions hold then 1105 is certainly composite, if they fail 1105 is probably prime)

    RonL
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Jun 2008
    Posts
    39

    Can you explain the last part of this to me?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    5
    Quote Originally Posted by duggaboy View Post

    Can you explain the last part of this to me?
    It is that these:

    "2^69(mod1105), 2^2*69(mod 1105), 2^4*69(mod1105), 2^8*69(mod1105)"

    are not congruent to -1 modulo 1105.

    RonL
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Row reduction Help
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: Jun 29th 2011, 07:01 PM
  2. Reduction to first order
    Posted in the Differential Equations Forum
    Replies: 1
    Last Post: May 18th 2010, 11:21 AM
  3. 3 log reduction
    Posted in the Algebra Forum
    Replies: 4
    Last Post: Apr 12th 2010, 07:38 AM
  4. 3 log reduction
    Posted in the Advanced Algebra Forum
    Replies: 0
    Last Post: Apr 12th 2010, 06:57 AM
  5. reduction of a cosΘ+/_ b sinΘ
    Posted in the Trigonometry Forum
    Replies: 2
    Last Post: Sep 21st 2009, 09:50 AM

Search Tags


/mathhelpforum @mathhelpforum