Generalizing algebraic factors on Riesel bases

[RichD]

Did we just reprove restate Aurifeuillian factors? :-)

[gd_barnes]

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

[gd_barnes]

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.

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.

[gd_barnes]

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.

[gd_barnes]

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

[CRGreathouse]

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.

[gd_barnes]

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.

[CRGreathouse]

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.

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:
http://pari.math.u-bordeaux.fr/download.html

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

[gd_barnes]

Excellent! Thanks.

[CRGreathouse]

If you have any trouble, let me know -- I'd be happy to help.