mersenneforum.org Generalizing algebraic factors on Riesel bases
 Register FAQ Search Today's Posts Mark Forums Read

 2010-04-04, 18:09 #23 RichD     Sep 2008 Kansas 3·17·59 Posts Did we just reprove restate Aurifeuillian factors? :-)
 2010-04-05, 22:17 #24 gd_barnes     May 2007 Kansas; USA 2×5,087 Posts Thanks guys for all of the input. I'll see how much of it I can absorb and may get back with you if I have some questions. One big reason I asked for this is that I want to incorporate algebraic factors into our starting bases script in the near future. Gary
2010-04-05, 22:20   #25
gd_barnes

May 2007
Kansas; USA

27BE16 Posts

Quote:
 Originally Posted by 10metreh For CRUS purposes: Here is a table of x and y for each b = 4m where b+1 (= f) is prime, from b = 250 to 1000. gd_barnes is probably the only person who will understand this. Code: 256 16, 241 268 82, 187 276 60, 217 280 53, 228 292 138, 155 (etc.)

Yep, I get it. lol Thanks. Saved me a bunch of time. Previously I had to manually come up with x and y values by trial and error.

It needs to be extended to base 1024 but thanks to you guys, I can come up with the rest of them fairly easily now without having to resort to the trial-and-error method.

Thanks again.

Last fiddled with by gd_barnes on 2010-04-05 at 22:21

2010-04-05, 22:26   #26
gd_barnes

May 2007
Kansas; USA

2×5,087 Posts

Quote:
 Originally Posted by 10metreh In which case you need to give gd_barnes a telling off too. After all he was the one who asked someone to "prove" it.
Yep, I knew that my original posting was a bunch of rambling that wasn't necessary and so I expected a bit of what others might call rambling in response.

Part of the reason that mine rambled so much is that it was something that was discovered over a period of 2 years and was edited over-and-over until the "pattern" of all such f became completely obvious to me; just in the last week. And...the reason it went on so long is that the project started out with only bases 3-32, then up to base 100, and then finally to base 1024.

2010-04-05, 23:29   #27
gd_barnes

May 2007
Kansas; USA

2×5,087 Posts

Quote:
 Originally Posted by Random Poster x=lift(sqrt(Mod(-1,p)))
I was able to understand most of the PARI code but could not understand the (Mod(-1,p)) part, even after googling a PARI tutorial. To me, (Mod(-1,p)) is the equivalent of saying:

z == (-1 mod p)

Therefore z would always have to be p-1. So wouldn't it be easier to code:
x=lift(sqrt(p-1)) ?

But that still doesn't make sense. Let me demonstrate:

First, I'll restate the entire PARI code given for reference and change it to where it would create a table of factors <= 1024:
for(m=1,255,p=4*m+1;if(isprime(p),x=lift(sqrt(Mod(-1,p)));print(4*m" "x", "p-x)))

Using an example for an f-value (factor) (or p-value in the PARI code) of 13, we have:

p=4*m+1 Let m=3 so that p=13.

Since p = 13 is prime, then:

x=lift(sqrt(Mod(-1,13)))

x=lift(sqrt(12))

x=lift(3.46)

How can x = 3.46? Even rounding up or down gives x = 3 or 4. But that is incorrect. For a factor (p-value) of 13, x must be 5 or 8 as previously demonstrated.

Can someone please tell me what I am missing?

10metreh, how did you come up with your f=250 thru 1000 table?

Gary

Last fiddled with by gd_barnes on 2010-04-05 at 23:54

2010-04-06, 00:50   #28
CRGreathouse

Aug 2006

11·13·41 Posts

Quote:
 Originally Posted by gd_barnes I was able to understand most of the PARI code but could not understand the (Mod(-1,p)) part, even after googling a PARI tutorial. To me, (Mod(-1,p)) is the equivalent of saying: z == (-1 mod p) Therefore z would always have to be p-1. So wouldn't it be easier to code: x=lift(sqrt(p-1)) ?
lift(sqrt(Mod(-1,p))) is the same as lift(sqrt(Mod(p-1,p))), but this is nothing like sqrt(p-1). sqrt(Mod(-1, p)) is the square root of -1 mod p, where sqrt(p-1) is the normal square root of p-1.

The square root of 12 is about 3.46. It is an irrational real number x such that x * x = 12.

The square root of 12 mod 13 is 5. It is an integer x such that x * x ≡ 12 (mod 13). 5 * 5 ≡ 25 ≡ 12 (mod 13).

Pari has a special type, intmod, for numbers modulo integers. Mod(12, 13) is not 12 but the object "12 mod 13". If you square 12 you get 144, but if you square Mod(12, 13) you get Mod(1, 13) since 12^2 ≡ 144 ≡ 1 (mod 13). lift() is a command that transforms intmods to integers by dropping the modulus. centerlift() is the other Pari command for converting intmods to integers; while lift() chooses the smallest positive representative, centerlift() chooses the one with the smallest absolute value. So lift(Mod(1, 13)) == centerlift(Mod(1, 13)) since they're both 1, but lift(Mod(12, 13)) == 12 while centerlift(Mod(12, 13)) == -1.

Last fiddled with by CRGreathouse on 2010-04-06 at 00:54

2010-04-06, 01:04   #29
gd_barnes

May 2007
Kansas; USA

2×5,087 Posts

Quote:
 Originally Posted by CRGreathouse lift(sqrt(Mod(-1,p))) is the same as lift(sqrt(Mod(p-1,p))), but this is nothing like sqrt(p-1). sqrt(Mod(-1, p)) is the square root of -1 mod p, where sqrt(p-1) is the normal square root of p-1. The square root of 12 is about 3.46. It is an irrational real number x such that x * x = 12. The square root of 12 mod 13 is 5. It is an integer x such that x * x ≡ 12 (mod 13). 5 * 5 ≡ 25 ≡ 12 (mod 13). Pari has a special type, intmod, for numbers modulo integers. Mod(12, 13) is not 12 but the object "12 mod 13". If you square 12 you get 144, but if you square Mod(12, 13) you get Mod(1, 13) since 12^2 ≡ 144 ≡ 1 (mod 13). lift() is a command that transforms intmods to integers by dropping the modulus. centerlift() is the other Pari command for converting intmods to integers; while lift() chooses the smallest positive representative, centerlift() chooses the one with the smallest absolute value. So lift(Mod(1, 13)) == centerlift(Mod(1, 13)) since they're both 1, but lift(Mod(12, 13)) == 12 while centerlift(Mod(12, 13)) == -1.

Ah, object oriented. I should have suspected as much. I've only had vague dealings with it in my programming career but enough to make clear sense of this now. Thanks for the detailed explanation.

Now that I understand it, that's a brilliant piece of code. Not so much in its complexity but in how short and simplistic that it is.

One of these days, I need to buy Pari and play around with it. For the various demonstrations I've seen on these forums, it's clearly very powerful.

Last fiddled with by gd_barnes on 2010-04-06 at 01:10

2010-04-06, 01:22   #30
CRGreathouse

Aug 2006

11·13·41 Posts

Yes, that's what I love about Pari: programs can be very short (and simple... but not simplistic). There's no need to mess around with all the stuff you'd have to do with lower-level, non-math-oriented languages.

Quote:
 Originally Posted by gd_barnes One of these days, I need to buy Pari and play around with it. For the various demonstrations I've seen on these forums, it's clearly very powerful.
Here's a copy:

It's free! And easy to learn, to boot.

Last fiddled with by CRGreathouse on 2010-04-06 at 01:23

 2010-04-06, 02:01 #31 gd_barnes     May 2007 Kansas; USA 2×5,087 Posts Excellent! Thanks.
 2010-04-06, 02:04 #32 CRGreathouse     Aug 2006 16E716 Posts If you have any trouble, let me know -- I'd be happy to help.

 Similar Threads Thread Thread Starter Forum Replies Last Post pepi37 Conjectures 'R Us 95 2017-07-04 13:37 R. Gerbicz Conjectures 'R Us 22 2009-12-29 20:21 Siemelink Conjectures 'R Us 105 2009-09-04 06:40 henryzz ElevenSmooth 13 2007-12-18 09:12 robert44444uk Conjectures 'R Us 139 2007-12-17 05:17

All times are UTC. The time now is 18:39.

Thu Aug 6 18:39:16 UTC 2020 up 20 days, 14:26, 2 users, load averages: 1.43, 1.70, 1.74