Results 1 to 4 of 4

Math Help - 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
    4
    Quote Originally Posted by duggaboy View Post
    let n=1105, so n-1=2^4\times 69 Compute the values of

    [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 1105 we have s=4 and d=69

    So a is a witness to the primallity of 1105 if:

     <br />
a^d \not \equiv 1 \mod 1105<br />

    and

     <br />
a^{2^r.d} \not \equiv -1 \mod 1105; \forall \ r \in \{0,\ ..., \ s-1\}<br />

    So if you compute the values asked for and the first is not congruent to \pm 1 \mod 1105 and the others are not congruent to -1 \mod 1105, then 2 is a witness to the compositness of 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
    4
    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: June 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: April 12th 2010, 07:38 AM
  4. 3 log reduction
    Posted in the Advanced Algebra Forum
    Replies: 0
    Last Post: April 12th 2010, 06:57 AM
  5. reduction of a cosΘ+/_ b sinΘ
    Posted in the Trigonometry Forum
    Replies: 2
    Last Post: September 21st 2009, 09:50 AM

Search Tags


/mathhelpforum @mathhelpforum