Register FAQ Search Today's Posts Mark Forums Read

 2009-01-09, 18:16 #34 henryzz Just call me Henry     "David" Sep 2007 Liverpool (GMT/BST) 598410 Posts does anyone know about a program that can output the full residue from a rabin-miller test and not just the RES64
2009-01-09, 18:23   #35
michaf

Jan 2005

479 Posts

Quote:
 Originally Posted by MooooMoo I'm not a vegetarian and have never been one, but keep in mind that I'll only give up beef if you find that residue. As Mini-Geek posted earlier, chicken, pork, lamb, fish, dairy products, etc are all fair game, so it wouldn't be that much of a lifestyle change for me. Good luck if you're trying to find that "BEEF15BAD" residue, you'll need it
123*2^6786786871-1 is not prime. LLR Res64: 12BEEF15BAD431DE

Hmm... Rather interesting :) No more beef for MooMoo ;)
(Or else prove that the residue is incorrect....)

2009-01-09, 18:27   #36
Mini-Geek
Account Deleted

"Tim Sorbera"
Aug 2006
San Antonio, TX USA

7×13×47 Posts

Quote:
 Originally Posted by michaf (Or else prove that the residue is incorrect....)
Sure, just give me a few thousand years.

2009-01-10, 10:40   #37
gd_barnes

May 2007
Kansas; USA

2×23×233 Posts

Quote:
 Originally Posted by michaf 123*2^6786786871-1 is not prime. LLR Res64: 12BEEF15BAD431DE Hmm... Rather interesting :) No more beef for MooMoo ;) (Or else prove that the residue is incorrect....)

Oh come on now, you can do better than that!

123*2^6786786871-1 cannot possibly have a residue of 12BEEF15BAD431DE. It has factors of 7 AND 13!! As I recall, that would mean that it would have a residue of 0000000000000007!

(no joke)

HARDY HARDY HARDY HA HA HA HA HA !!!!!!!!!!!!!!!

Lest anyone wonder how I came up with that: My good old mainstay...Alpertron's site. All I did was calculate the values for all n=1 thru 30 and found the following patterns:

For all 123*2^n-1, all n==(1 mod 3) has a factor of 7 and all n==(7 mod 12) has a factor of 13. 6786786871 is both == (1 mod 3) and == (7 mod 12).

Mike, you can continue eating beef.

Sometimes I even amaze myself.

Gary

2009-01-10, 12:08   #38
michaf

Jan 2005

1110111112 Posts

Quote:
 Originally Posted by gd_barnes Oh come on now, you can do better than that! 123*2^6786786871-1 cannot possibly have a residue of 12BEEF15BAD431DE. It has factors of 7 AND 13!! As I recall, that would mean that it would have a residue of 0000000000000007! (no joke) HARDY HARDY HARDY HA HA HA HA HA !!!!!!!!!!!!!!! Lest anyone wonder how I came up with that: My good old mainstay...Alpertron's site. All I did was calculate the values for all n=1 thru 30 and found the following patterns: For all 123*2^n-1, all n==(1 mod 3) has a factor of 7 and all n==(7 mod 12) has a factor of 13. 6786786871 is both == (1 mod 3) and == (7 mod 12). Mike, you can continue eating beef. Sometimes I even amaze myself. Gary
okok... I haven't had put any effort in it :)
I didn't even check for small factors :0

Continue to eat your beef :)

2009-01-10, 13:24   #39
Mini-Geek
Account Deleted

"Tim Sorbera"
Aug 2006
San Antonio, TX USA

7·13·47 Posts

Quote:
 Originally Posted by gd_barnes 123*2^6786786871-1 cannot possibly have a residue of 12BEEF15BAD431DE. It has factors of 7 AND 13!! As I recall, that would mean that it would have a residue of 0000000000000007!
Can this be tested? LLR rejects anything with such a trivial factor, so what about something with a lowest factor that'd still fit in the residue size?
Quote:
 Originally Posted by gd_barnes Lest anyone wonder how I came up with that: My good old mainstay...Alpertron's site. All I did was calculate the values for all n=1 thru 30 and found the following patterns: For all 123*2^n-1, all n==(1 mod 3) has a factor of 7 and all n==(7 mod 12) has a factor of 13. 6786786871 is both == (1 mod 3) and == (7 mod 12).
Patterns != Proof, Law of Small Numbers, etc.
Do you have any mathematical proof (even if I couldn't understand it ) that all 123*2^n-1 with n==(1 mod 3) has a factor of 7 or that all n==(7 mod 12) has a factor of 13?
Quote:
 Originally Posted by gd_barnes Mike, you can continue eating beef.
Oh, I'm sure he can for now anyway. Is there anything that can actually try to factor something that large to show certainly that it has trivial factors?
Quote:
 Originally Posted by gd_barnes Sometimes I even amaze myself.
Oh Lord it's hard to be humble, when you're perfect in every way!

2009-01-10, 14:13   #40
S485122

"Jacob"
Sep 2006
Brussels, Belgium

3·5·112 Posts

Quote:
 Originally Posted by Mini-Geek Do you have any mathematical proof (even if I couldn't understand it ) that all 123*2^n-1 with n==(1 mod 3) has a factor of 7 or that all n==(7 mod 12) has a factor of 13?
n==1 mod 3.
n=3*m+1.
123*2^n-1=123*2^(3*m+1)-1=123*2*2^(3*m)-1
2^3==1 mod 7 => 2^(3*m)=(2^3)^m==1 mod 7
123*2*2^(3*m)-1==246*1-1 mod 7
245==0 mod 7

Use the same path for the other case.

Jacob

2009-01-10, 17:45   #41
henryzz
Just call me Henry

"David"
Sep 2007
Liverpool (GMT/BST)

25×11×17 Posts

Quote:
 Originally Posted by henryzz does anyone know about a program that can output the full residue from a rabin-miller test and not just the RES64
i think this got buried

2009-01-11, 09:00   #42
gd_barnes

May 2007
Kansas; USA

2·23·233 Posts

Quote:
 Originally Posted by S485122 n==1 mod 3. n=3*m+1. 123*2^n-1=123*2^(3*m+1)-1=123*2*2^(3*m)-1 2^3==1 mod 7 => 2^(3*m)=(2^3)^m==1 mod 7 123*2*2^(3*m)-1==246*1-1 mod 7 245==0 mod 7 Use the same path for the other case. Jacob

Nicely stated. Call it the "law of modulo arithmetic".

2009-01-11, 14:35   #43
Mini-Geek
Account Deleted

"Tim Sorbera"
Aug 2006
San Antonio, TX USA

10B516 Posts

Quote:
 Originally Posted by S485122 n==1 mod 3. n=3*m+1. 123*2^n-1=123*2^(3*m+1)-1=123*2*2^(3*m)-1 2^3==1 mod 7 => 2^(3*m)=(2^3)^m==1 mod 7 123*2*2^(3*m)-1==246*1-1 mod 7 245==0 mod 7 Use the same path for the other case. Jacob
Quote:
 Originally Posted by Mini-Geek (even if I couldn't understand it )
Looks like that part turned out to be true (partially). I don't understand this part:

2^3==1 mod 7 => 2^(3*m)=(2^3)^m==1 mod 7

Why do we know that 2^(3*m)==1 mod 7 is equivalent to 2^3==1 mod 7? Is it just a law/thereom/whatever that there's no further explanation to or is there a reason that could be explained?

2009-01-11, 17:31   #44
S485122

"Jacob"
Sep 2006
Brussels, Belgium

34278 Posts

Quote:
 Originally Posted by Mini-Geek Looks like that part turned out to be true (partially). I don't understand this part: 2^3==1 mod 7 => 2^(3*m)=(2^3)^m==1 mod 7 Why do we know that 2^(3*m)==1 mod 7 is equivalent to 2^3==1 mod 7? Is it just a law/thereom/whatever that there's no further explanation to or is there a reason that could be explained?
2^(3*m)=(2^3)^m
(2^3)^m=8^m
8^m=(7+1)^m
(7+1)^m==(0+1)^m mod 7
1^m=1
so
2^(3*m)==1 mod 7

Jacob

 Similar Threads Thread Thread Starter Forum Replies Last Post a nicol Miscellaneous Math 21 2017-12-19 11:34 Oddball Lounge 7 2011-04-02 16:59 only_human Lounge 17 2008-07-17 23:58 ewmayer Lounge 2 2007-11-02 04:21 Orgasmic Troll Lounge 2 2003-12-05 12:16

All times are UTC. The time now is 03:27.

Wed May 25 03:27:45 UTC 2022 up 41 days, 1:29, 0 users, load averages: 1.49, 1.88, 2.00