mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Miscellaneous Math

Reply
 
Thread Tools
Old 2011-05-18, 17:28   #34
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts
Default

Quote:
Originally Posted by science_man_88 View Post
Wikipedia would lead me to believe this means that q^2 mod q = p using that search.
though other searching seems to point towards:

http://en.wikipedia.org/wiki/Multiplicative_order and solving for k=p for mod q and base a or what ever.
science_man_88 is offline   Reply With Quote
Old 2011-05-18, 21:41   #35
jyb
 
jyb's Avatar
 
Aug 2005
Seattle, WA

1,567 Posts
Default

Quote:
Originally Posted by science_man_88 View Post
I can't quite get what a order 2 modulo is ( I've google searched and still can't find a simple answer).
The (multiplicative) order of b modulo n (which I think is what you're asking about) is defined to be the least positive number k such that b^k == 1 (mod n). Here n and b are assumed to be coprime.

So for example, the order of 2 mod 7 is 3, since 2^3 == 1 (mod 7) and there is no smaller positive exponent for which that would be true. On the other hand, the order of 3 mod 7 is 6 (try looking at the powers of 3 mod 7 to verify this for yourself).

An important fact about multiplicative orders is that if b^k == 1 (mod n), then the order of b mod n must divide k. See if you can prove this for yourself. For example, 4^6 == 1 (mod 21), so the order of 4 mod 21 must divide 6. And indeed, you can check that it's 3.
jyb is offline   Reply With Quote
Old 2011-05-18, 21:44   #36
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts
Default

Quote:
Originally Posted by jyb View Post
The (multiplicative) order of b modulo n (which I think is what you're asking about) is defined to be the least positive number k such that b^k == 1 (mod n). Here n and b are assumed to be coprime.

So for example, the order of 2 mod 7 is 3, since 2^3 == 1 (mod 7) and there is no smaller positive exponent for which that would be true. On the other hand, the order of 3 mod 7 is 6 (try looking at the powers of 3 mod 7 to verify this for yourself).

An important fact about multiplicative orders is that if b^k == 1 (mod n), then the order of b mod n must divide k. See if you can prove this for yourself. For example, 4^6 == 1 (mod 21), so the order of 4 mod 21 must divide 6. And indeed, you can check that it's 3.
I'm asking more about the quote from the OEIS I made because I kinda want to find other relations other than the p=4k+3 and q=2p+1 situation the quote talks of. I don't get what it's talking of the multiplicative article I found on Wikipedia is the one that even makes sense to me but I'm likely wrong. I can't quite figure out the other articles suggested

Last fiddled with by science_man_88 on 2011-05-18 at 21:46
science_man_88 is offline   Reply With Quote
Old 2011-05-18, 23:42   #37
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

134458 Posts
Default

sm: Try

znorder(Mod(2,101))

and the like.
CRGreathouse is offline   Reply With Quote
Old 2011-05-19, 00:05   #38
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

203008 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
sm: Try

znorder(Mod(2,101))

and the like.
okay I see kinda what znorder does , the problem is I still don't see what the quoted material means.
science_man_88 is offline   Reply With Quote
Old 2011-07-22, 19:40   #39
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26·131 Posts
Default Lucas Lehmer test

okay I'm back , this time about something I see that might drop a step in the LL test:

is there a way to test to find y:

IF x \equiv 2 \text { mod p}
then \sqrt{x} \equiv \text {y mod p}

if so we can take the LL test down one step , because if S_{n}+2 \equiv 2 \text { mod p} then S_{n-1} \equiv \text {y mod p}
science_man_88 is offline   Reply With Quote
Old 2011-07-22, 21:41   #40
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts
Default

Quote:
Originally Posted by science_man_88 View Post
okay I'm back , this time about something I see that might drop a step in the LL test:

is there a way to test to find y:

IF x \equiv 2 \text { mod p}
then \sqrt{x} \equiv \text {y mod p}

if so we can take the LL test down one step , because if S_{n}+2 \equiv 2 \text { mod p} then S_{n-1} \equiv \text {y mod p}
I found :

http://mathforum.org/library/drmath/view/66757.html

if applied generally instead of just to 2 it might be able to get it back to the first S_{n}\gt {M_{p}} would that speed things up ? though I'm kinda confused about what I found.

Last fiddled with by science_man_88 on 2011-07-22 at 21:42
science_man_88 is offline   Reply With Quote
Old 2011-07-23, 01:57   #41
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26·131 Posts
Default

just realized something using PARI:

Code:
(22:43)>for(x=1,7,print((x^2)%7"::"x","))
1::1,
4::2,
2::3,
2::4,
4::5,
1::6,
0::7,
note how the x that have remainder 2 are 2^w and the mersenne-2^w this seems to work so far using 31 and 127 as well. so S_{n-1} \equiv +/-2^w \text { mod the Mersenne chosen} and yes I know 2 possible remainders not 1. 2^w starts at w=2 and seems to work w up one every odd number after p=3. that's all I have for now.
science_man_88 is offline   Reply With Quote
Old 2011-07-24, 01:09   #42
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

203008 Posts
Default

Quote:
Originally Posted by science_man_88 View Post
just realized something using PARI:

Code:
(22:43)>for(x=1,7,print((x^2)%7"::"x","))
1::1,
4::2,
2::3,
2::4,
4::5,
1::6,
0::7,
note how the x that have remainder 2 are 2^w and the mersenne-2^w this seems to work so far using 31 and 127 as well. so S_{n-1} \equiv +/-2^w \text { mod the Mersenne chosen} and yes I know 2 possible remainders not 1. 2^w starts at w=2 and seems to work w up one every odd number after p=3. that's all I have for now.
just realized something while rereading this post: M_P=odd so they alternate I think the problem is for me to figure out which one it falls on.
science_man_88 is offline   Reply With Quote
Old 2011-07-26, 02:02   #43
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

20C016 Posts
Default

Quote:
Originally Posted by science_man_88 View Post
just realized something while rereading this post: M_P=odd so they alternate I think the problem is for me to figure out which one it falls on.
figured out how to relate w back to p:

w=(p+1)/2 = ceil(p/2)

so can we use this to relate the next step to a mod p ?
science_man_88 is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Basic Number Theory 5: rationals & intro to modular arithmetic Nick Number Theory Discussion Group 1 2016-10-21 22:21
modular arithmetic problem JuanTutors Math 4 2009-03-11 16:06
need C/C++ modular arithmetic code for Windows ixfd64 Programming 15 2008-07-30 03:52
Modular Arithmetic Numbers Math 27 2005-11-30 15:41
Jim Howell's modular arithmetic program? ixfd64 Software 0 2004-05-27 05:42

All times are UTC. The time now is 22:32.

Wed Sep 30 22:32:26 UTC 2020 up 20 days, 19:43, 0 users, load averages: 1.72, 1.57, 1.50

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.