Are Legendre symbols proven to be defective?
 

It's not going to surprise me if this gets put in Miscellaneous Math, or hurt my feelings, but I'm going to try to phrase things in order to avoid getting this thread switched over. I know I'm way out of my league with these questions, but a friend of mine, who I very much respect, brought these to my attention. He swore me to secrecy, for reasons I'm not prepared to disclose, so I'm going to be asking questions that may not seem to be connected.

(1) The Legendre symbol method of sieving,(sorry if this is nonsensical, I'm hoping I can make myself understood), is it 100% proven, or is it simply BELIEVED to be 100% effective?

(2) The idea that a Fermat prime cannot have odd prime factors in the exponent, is it proven, or just BELIEVED to be effective? If I give a number, like 2^68544+1, can you give me an actual factor with that information, or is it mathematics that makes you believe it has a factor? Are there ANY gaps in the reasoning?

(3) How many of the top-5000 primes have been tested via integer based math? After that twin prime fiasco with Intel, wouldn't it be better to test numbers with an integer based test after the normal test is run?

As I said, there's a lot of stuff that I'm suppressing on request. My friend has told me(approximate quote),"A lot of the stuff that people accept as fact is not true, so-and-so(note: I'm not telling who or what was mentioned, but it isn't George :) ) intentionally stacked the deck so that they would find the first 10-million digit prime. Because of this, a lot of primes on the top-5000 list are actually composite. You(jasong) have the necessary skills to figure it out with a good amount of work." From the way he said it(as I said, it's an approximate quote), it sounds like people have discovered what he discovered in the past(further than you would believe) and it is being suppressed.

Lastly, is there an integer based prime testing program that would work on an x86 LInux box? If I could get my hands on one and use it, I could establish 100% in my own mind that I wasn't simply being taken for a ride. I don't think my friend is a liar, but there are only two possibilities left, delusional and genius. I badly want to believe it's the latter, but I don't have the education to have a worthwhile opinion. Right now, it's totally up in the air.

Aren't conspiracy theories so much fun? :smile:

jasong: You can use [url=http://snipurl.com/gfgidude"]google[/url] to answer your questions within just a few minutes. I think it took you longer to type your question than it would take to search for the answer yourself.

[QUOTE=retina;128960]jasong: You can use [url=http://snipurl.com/gfgidude"]google[/url] to answer your questions within just a few minutes. I think it took you longer to type your question than it would take to search for the answer yourself.[/QUOTE]
As I said, it will take me a good amount of work to get my education to the level where I can answer my own question. If this is being suppressed, then it's doubtful it could be found easily on the web.

As an example, what form of government is in effect in the United States? Most people would say "democracy" without even thinking about it, but the word democracy isn't in any state Constitution, nor is it in any of the major documents of the US government. Democracy is just a feel-good term that the politicians employ to control our emotions. If you look it up on the web, there's a good chance you'll receive erroneous information, even from a so-called expert. We are a constitutional republic.

If the mathematics is being suppressed, there's a good chance that Wikipedia is part of that. It would simply be a matter of a government employee working from home, so that there's no .gov extension on the name.


That being said, my IQ is extremely high, I took my last IQ test while I was badly delusional, and still managed to stun my advisor. If I wasn't a paranoid schizophrenic, I'd probably be another super-conceited R.D. Silverman type. It's only recently, with the help of a medication called Invega, that I've gotten to a place where I can try to get back to a normal life. My point is that if there's any hanky-panky going on anywhere, and from a value-based standpoint I'll tackle any form of lying out there, I'm a good person to find it.

Okay, go ahead and place this in Miscellaneous Math, or probably more appropriately, Soap Box, :) since I've probably lost all credibility in this thread. :)

Edit: On second thought, can we leave it here, and split off any Conspiracy theory stuff?

If I wanted to take all the numbers that NewPGen threw out after sieving to a billion, from the 66 Riesel ks that are left, and test them independently for the factor given, would anyone be willing to help me do that?

I say Riesel ks, but I'm willing to consider other possibilities. :)

Edit: try sieving, with newpgen, with k*2^n+1, for k=1 to 5, and n=3355583. And then, if possible, tell me the factor for 2*2^3355583+1, with newpgen if you can manage it, but some other way if newpgen won't tell you and you know another way.

A couple of comments:
(1) I cannot answer jasong's questions because I am not a specialist. However I am very interested in reading answers from others here who are specialists in the field. Considering that he has asked very specific questions - certainly his questions 2 and 3 are specific, and probably 1 is as well but I don't know what the "Legendre symbol method" means - I think he deserves specific answers instead of being referred to Google. One advantage of well-posed questions being answered here is that we generally know the person who is answering, any inaccuracies that are made can be corrected by others, and it might generate further interesting discussion. Lots of us would like to read that.
(2) Jasong, I cannot myself believe in any conspiracy theory because the mathematics involved is public knowledge and testable independently by specialists all over the world using their own independently written software. Cover-ups can only occur if the information is secret or computationally inaccessible to all but the insiders. In the case of the top 5000 primes, the huge effort needed was in discovering them in the first place, not in verifying their prime status.

Jasong,


Write n = e*o, where e is even and o is odd. Then

1 + 2^n = 1 + 2^(e*o) = 1 + (2^e)^o = 1 + ((2^e+1) - 1)^o =

1 + (-1)^o = 0 mod (2^e+1).

Thus 2^e+1 divides 1 + 2^n.


Regards,


Joseph

[QUOTE=jasong;128958]It's not going to surprise me if this gets put in Miscellaneous Math, or hurt my feelings, but I'm going to try to phrase things in order to avoid getting this thread switched over. I know I'm way out of my league with these questions, but a friend of mine, who I very much respect, brought these to my attention. He swore me to secrecy, for reasons I'm not prepared to disclose, so I'm going to be asking questions that may not seem to be connected.

(1) The Legendre symbol method of sieving,(sorry if this is nonsensical, I'm hoping I can make myself understood), is it 100% proven, or is it simply BELIEVED to be 100% effective?

(2) The idea that a Fermat prime cannot have odd prime factors in the exponent, is it proven, or just BELIEVED to be effective? If I give a number, like 2^68544+1, can you give me an actual factor with that information, or is it mathematics that makes you believe it has a factor? Are there ANY gaps in the reasoning?

(3) How many of the top-5000 primes have been tested via integer based math? After that twin prime fiasco with Intel, wouldn't it be better to test numbers with an integer based test after the normal test is run?

As I said, there's a lot of stuff that I'm suppressing on request. My friend has told me(approximate quote),"A lot of the stuff that people accept as fact is not true, so-and-so(note: I'm not telling who or what was mentioned, but it isn't George :) ) intentionally stacked the deck so that they would find the first 10-million digit prime. Because of this, a lot of primes on the top-5000 list are actually composite. You(jasong) have the necessary skills to figure it out with a good amount of work." From the way he said it(as I said, it's an approximate quote), it sounds like people have discovered what he discovered in the past(further than you would believe) and it is being suppressed.

Lastly, is there an integer based prime testing program that would work on an x86 LInux box? If I could get my hands on one and use it, I could establish 100% in my own mind that I wasn't simply being taken for a ride. I don't think my friend is a liar, but there are only two possibilities left, delusional and genius. I badly want to believe it's the latter, but I don't have the education to have a worthwhile opinion. Right now, it's totally up in the air.[/QUOTE]

I would answer your questions if I could figure out what you were asking.
Your questions consist largely of "word salad".

(1)
What does it mean for a theorem to be "100% effective"? I know how
mathematicians use the word "effective", but that is clearly not what you
mean here. Analytic number theorists use the word effective to describe
a theorem where the implied constants in asymptotic (and other) estimates
are explicitly known or can be computed. What do YOU mean?????

(2)
What do you mean by the "Legendre symbol method of sieving"? Please
specify the exact sieve algorithm and its context. AFAIK, there is no such
method of sieving. One might use Legendre symbols in a sieve pre-computation, but I doubt if they are used during the actual sieve; their
computation would be too slow.

(3)
For your second question, Fermat numbers are of the form 2^2^n + 1.
It follows immediately from their definition that the exponent is even.
What does "belief" have to do with it? And the word "effective" is again
word salad. And the rest of the question is gibberish.

(4) As for how many of the top 5000 primes have been tested by purely
integer methods, I doubt anyone knows. What difference does it make?
The prior Intel FP bug is now a red herring. The problem has been corrected.
People have thoroughly checked the current IA32 chips for their FP
correctness.

(5)
Who is this "friend"? He is clearly clueless.

(6)
I suggest that you consult a psychiatrist for your unreasoned paranoia.

[QUOTE=jasong;128958]If I give a number, like 2^68544+1, can you give me an actual factor with that information[/QUOTE]

68544 = 64 * 9 * 7 * 17

Hence the following are all algebraic factors of 2[sup]68544[/sup]+1:

2[sup]64[/sup]+1
2[sup]64*3[/sup]+1
2[sup]64*7[/sup]+1
2[sup]64*9[/sup]+1
2[sup]64*17[/sup]+1
2[sup]64*3*7[/sup]+1
2[sup]64*3*17[/sup]+1
2[sup]64*7*17[/sup]+1
2[sup]64*9*7[/sup]+1
2[sup]64*9*17[/sup]+1
2[sup]64*3*7*17[/sup]+1

[QUOTE=wblipp;128989]68544 = 64 * 9 * 7 * 17

Hence the following are all algebraic factors of 2[sup]68544[/sup]+1:

2[sup]64[/sup]+1
2[sup]64*3[/sup]+1
2[sup]64*7[/sup]+1
2[sup]64*9[/sup]+1
2[sup]64*17[/sup]+1
2[sup]64*3*7[/sup]+1
2[sup]64*3*17[/sup]+1
2[sup]64*7*17[/sup]+1
2[sup]64*9*7[/sup]+1
2[sup]64*9*17[/sup]+1
2[sup]64*3*7*17[/sup]+1[/QUOTE]

This is just 1st or second year junior high school polynomial algebra.
x^ab + 1 is divisible by x^a+1 when b is odd. I would have expected
even Jason to know this.

[QUOTE=R.D. Silverman;128985]I would answer your questions if I could figure out what you were asking.
Your questions consist largely of "word salad".

[quote](1)
What does it mean for a theorem to be "100% effective"? I know how
mathematicians use the word "effective", but that is clearly not what you
mean here. Analytic number theorists use the word effective to describe
a theorem where the implied constants in asymptotic (and other) estimates
are explicitly known or can be computed. What do YOU mean?????[/quote]
You didn't quote what I said, and I have a bad memory, so I'll have to come back to this later if it starts looking important.

[quote](2)
What do you mean by the "Legendre symbol method of sieving"? Please
specify the exact sieve algorithm and its context. AFAIK, there is no such
method of sieving. One might use Legendre symbols in a sieve pre-computation, but I doubt if they are used during the actual sieve; their
computation would be too slow.[/quote]
My friend claimed that Legendre symbols weren't a proven method of determining whether a number was a likely candidate to sieved by a p-value. Remember, a lot of times we're dealing with millions of k/n pairs, so if it was wrong, say, 1/10,000,000th of the time, people wouldn't necessarily know, but it would still be wrong.

[quote](3)
For your second question, Fermat numbers are of the form 2^2^n + 1.
It follows immediately from their definition that the exponent is even.
What does "belief" have to do with it? And the word "effective" is again
word salad. And the rest of the question is gibberish.[/quote]
Again, you didn't quote me, but my friend claims that NewPGen spits out the number 2^3355584+1 as having a factor of 2, which is clearly impossible. For the lower number, I just made up my own.

[quote](4) As for how many of the top 5000 primes have been tested by purely
integer methods, I doubt anyone knows. What difference does it make?
The prior Intel FP bug is now a red herring. The problem has been corrected.
People have thoroughly checked the current IA32 chips for their FP
correctness.[/quote]
Intel SAYS the error has been corrected. For most applications, for instance games, video and audio compression software, and probably other stuff I can't think of at the moment, small errors don't matter at all. For something like LLR, they would matter very much.

[quote](5)
Who is this "friend"? He is clearly clueless.[/quote]
I could say the same about you, just not on the subject of math. Have you ever heard of the golden rule?

[quote](6)
I suggest that you consult a psychiatrist for your unreasoned paranoia.[/quote]
I suggest you consult a life coach on personal etiquette. This has gone beyond sniping in your case, and I'm not simply talking about our encounters.

[QUOTE]Again, you didn't quote me, but my friend claims that NewPGen spits out the number 2^3355584+1 as having a factor of 2, which is clearly impossible.[/QUOTE]

GIGO

[QUOTE=jasong;128994][QUOTE=R.D. Silverman;128985]


I could say the same about you, just not on the subject of math. Have you ever heard of the golden rule?


I suggest you consult a life coach on personal etiquette. This has gone beyond sniping in your case, and I'm not simply talking about our encounters.[/QUOTE]

I am not politically correct. When someone spouts nonsense, I say so.
When someone exhibits clear signs of paranoia, I say so. This is a
public forum. When the town fool spouts nonsense on the street corner
he can expect to be criticized. And I wasn't criticizing YOU, I was
criticizing your friend.

I am clueless about many things. When and if I were to speak
gibberish about one of them then strong criticism would be
appropriate. But your "friend" was discussing
mathematics. And in this regard he clearly is clueless.

And I am not the only one to suggest that you need help with your
paranoia.

[QUOTE=paulunderwood;128996]GIGO[/QUOTE]
lol, it was a computer program, and the number was entered as 2*2^3355583+1. Unless you're badly stating that Paul Jobling made a buggy program, GIGO most definitely does NOT apply here.

Edit: I'm not suggesting that Mr. Jobling is at fault, but I think people need to seriously consider the possibility that, when determining whether a p-value is a possible divisor, Legendre symbols aren't totally dependable. I don't have the math skills to prove it, but I have tremendous amount of respect for my unnamed friend, and that is his opinion.

While I may not look that intelligent on Mersenne Forum, and the fiasco that occurred regarding me and the No Prime Left Behind project only makes that view worse, I can assure you that my ability to reason ranks pretty high. In my opinion, the problem is that I suggest things that could be clarified in about 5 minutes of real-world conversation, but Mersenne Forum is not even close to that medium.

[QUOTE=jasong;129001]

Edit: I'm not suggesting that Mr. Jobling is at fault, but I think people need to seriously consider the possibility that, when determining whether a p-value is a possible divisor, Legendre symbols aren't totally dependable. I don't have the math skills to prove it, but I have tremendous amount of respect for my unnamed friend, and that is his opinion.

[/QUOTE]

Would someone else care to take a crack at determining what

"determining whether a p-value is a possible divisor, Legendre symbols aren't totally dependable"

might mean??? What does it mean for a mathematical function to be
undependable? Was this phrase formulated by someone on
Quaaludes????

[QUOTE=R.D. Silverman;129005]
Would someone else care to take a crack at determining what

"determining whether a p-value is a possible divisor, Legendre symbols aren't totally dependable"

might mean??? What does it mean for a mathematical function to be
undependable? Was this phrase formulated by someone on
Quaaludes????[/QUOTE]
I think he's referring to the sieve-based precomputations for Riesel-like projects, that use big tables and legendre symbols to eliminate candidate numbers before proceeding to a proth test. Or not <shrug>

On another note, you may be the last person left who actually uses the word 'quaaludes'.

[QUOTE=R.D. Silverman;128990]This is just 1st or second year junior high school polynomial algebra. x^ab + 1 is divisible by x^a+1 when b is odd. I would have expected even Jason to know this.[/QUOTE]


You're assessment of Jason's mathematical sophistication exceeds mine. When somebody asks "can you show me a factor." I assume they don't know how to find a factor.

[QUOTE=jasong;128958](2) The idea that a Fermat prime cannot have odd prime factors in the exponent, is it proven, or just BELIEVED to be effective?[/quote]
It can easily and rigorously be shown that 2[sup]n[/sup]+1 can be prime iff n is a power of 2. End of story there.

[quote](3) How many of the top-5000 primes have been tested via integer based math? After that twin prime fiasco with Intel, wouldn't it be better to test numbers with an integer based test after the normal test is run?[/quote]
I expect very few, if any, of the ones above 10000 digits. But that is not due to some Intel-sponsored conspiracy amongst computationalists, but rather for a simple practical reason, namely that to test such large primes invariably requires many multiplies modulo same, and on modern computer hardware this is significantly faster [anywhere from 2-10x, depending on the code and the modulus] using floating-point-based convolution [i.e. FFT or some similar kind of discrete transform] than integer-based. This is not because integer multiply [and hardware multiply is the bottleneck in all such cases] is intrinsically harder to do than floating-point - quite the opposite, in fact - but rather because hardware manufacturers have thrown much more silicon at floating-point units on their chips. That's because relatively few "real world" applications need screamingly fast general-purpose integer multiply - most programs running on a typical PC need integer MUL mainly for address computations, and for the standard hardware-supported data types such address computations can instead be done using cheaper shift/add arithmetic.

[quote]As I said, there's a lot of stuff that I'm suppressing on request. My friend has told me(approximate quote),"A lot of the stuff that people accept as fact is not true, so-and-so(note: I'm not telling who or what was mentioned, but it isn't George :) ) intentionally stacked the deck so that they would find the first 10-million digit prime. Because of this, a lot of primes on the top-5000 list are actually composite. You(jasong) have the necessary skills to figure it out with a good amount of work." From the way he said it(as I said, it's an approximate quote), it sounds like people have discovered what he discovered in the past(further than you would believe) and it is being suppressed.[/quote]
And you actually bought into this stereotypical crank paranoia? It's not as if projects like GIMPS operate in secret - we test prime candidates as fast as we can given the software and user base, and the prime-candidate "wavefront" advances accordingly. Sure, some projects deliberately try to winnow their prime candidates down and not bother with the lower ranges so as to get to the next artificial milestone first, but anyone is free to try their hand at this sort of thing. So pray tell [or pray ask your buddy Deep Throat]: in what way is the "deck being stacked?" If he really has a program that is 100x faster than the LL test as you've repeatedly claimed, surely he has managed thereby to stacxk the deck in his own favor?

Also, I've little doubt that at least some nonvanishing fraction of the top 5000 were incorrectly flagged as prime - any of the ones small enough to not be of much interest [i.e. most of them] and tested just once or using the same software twice without the kinds of independent-data-on-both-runs requirements GIMPS places on double checks is a candidate for bogus primehood, but "lots?" I suggest as a simple "bullshit check" to ask your friend to point out [say] 10 of the 5000 which are in fact composite. If his claim of "lots" is true, that should be easy. I'm predicting he'll come bacxk with some cryptic Yoda-like response that puts the burden of proof on you, e.g. "Trust your feelings and search diligently, you must."

[quote]Lastly, is there an integer based prime testing program that would work on an x86 LInux box? If I could get my hands on one and use it, I could establish 100% in my own mind that I wasn't simply being taken for a ride. I don't think my friend is a liar, but there are only two possibilities left, delusional and genius. I badly want to believe it's the latter, but I don't have the education to have a worthwhile opinion. Right now, it's totally up in the air.[/QUOTE]
AFAIK Jasonp's integer-based code [which uses an efficient small-prime modulus, the Mersenne M61] is the fastest of the lot. And for the record, I vote "delusional" - the patently ridiculous "will blow LL test out of the water ... 100x faster..." claims you've been making on his behalf cinch that as far as I'm concerned. On your part, you readily admit you lack the education to judge such things, yet you say that your Secret Subgenius buddy trusts you to crack the Mystery of the Stealth Composites lurking amongst the Top 5000 list. That should concern you right there - recall the old Groucho Marx quote about refusing to join any club that would have him as a member.

And please, don't ask me to provide you with links to and how-to-use instructions for jasonp's code - a simple websearch will get you there.

[QUOTE=jasonp;129007]On another note, you may be the last person left who actually uses the word 'quaaludes'.[/QUOTE]

Yes, Bob is dating himself, but Bob has an admirably reckless disregard for fashion and fads. The rest of us, slaves to hipster trends as we are, probably would prefer more up-to-date jargon such as "Dude, put down the crack pipe!" or even more trendily, the text-message-y "d00d, R U Hi?"

Okay, obviously the shit has hit the fan by now, so I'll throw my own shit now.

If you tell NewPGen to sieve k=1 to 5 for the equation k*2^3355583+1, it will say everything has been sieved and all have been found composite, and it will do that in less than a second.

Given that, it should be simple for any of you braggarts to track down a factor of 2^3355584+1, and then run a doublecheck on that factor that doesn't use shortcuts. I predict that if you go through with this, you'll fail either on the first task, or the factor will be proven wrong on the second task.

If you can supply me with a factor and post it, then I will go to my friends at Riesel Sieve, who find me entertaining, if not intelligent, and ask them to duplicate the test. Because I really don't trust you guys to be honest about this, not because I'm delusional, but because a lot of people on here(I'll leave wblipp out of this, since this seems to be the first time he's been disrespectful to me, maybe some others deserve the same honor) seem to be extremely proud of their accomplishments, while my values won't even let me read self-esteem literature without getting offended.

There are a lot of jackasses on this forum, and I would venture to say that the so-called crackpots tend to deserve more respect than the people who seem to exist to degrade them.

If you have a tendency to show respect to people who don't understand number theory, my hat's off to you. Negative energy is more powerful than positive energy, which is the reason high-mindedness needs to be nurtured wherever it is found. With the things my friend told me, I have lost almost all interest in prime number projects, though wblipp may continue to get my computer time, simply because I've found him to be respectful a majority of the time.(99% it looks like, maybe more) And of course, OPN project primes are verified in a different fashion, by necessity.

I'll repeat my challenge. Find a factor for 2^3355584+1 and test it without shortcuts. If my friends(or tolerators, possibly) at Riesel Sieve tell me that they've duplicated the result, then I'll shut up. Otherwise, you should seriously consider showing so-called cranks more respect.

[quote=jasong;129019]If you tell NewPGen to sieve k=1 to 5 for the equation k*2^3355583+1, it will say everything has been sieved and all have been found composite, and it will do that in less than a second.

Given that, it should be simple for any of you braggarts to track down a factor of 2^3355584+1, and then run a doublecheck on that factor that doesn't use shortcuts. I predict that if you go through with this, you'll fail either on the first task, or the factor will be proven wrong on the second task.[/quote]
Using the latest sr1sieve, I found that 2^3355584+1 is divisible by 5. I verified the factor with Pari/GP (which as far as I know uses plain old straight division, with no "shortcuts"). :smile:

[QUOTE=jasong;129019]Given that, it should be simple for any of you braggarts to track down a factor of 2^3355584+1, and then run a doublecheck on that factor that doesn't use shortcuts. [/QUOTE]

Using the same high school algebra that Dr. Silverman so generously assumed you would know - because 3355584 = 64 * 3 * 17477, it has the following algebraic factors,

2[sup]64[/sup]+1
2[sup]64*3[/sup]+1
2[sup]64*17477[/sup]+1

All can be checked with pencil and paper using numbers no larger than the exponents themselves and the previously mentioned high school algebra.

[QUOTE=jasong;129019]then I'll shut up.[/QUOTE]

It's time to deliver on this. You should check your meds before posting again. I think you're going to be sorry about some of these posts tomorrow or the next day.

William

[quote=Anonymous;129022]Using the latest sr1sieve, I found that 2^3355584+1 is divisible by 5. I verified the factor with Pari/GP (which as far as I know uses plain old straight division, with no "shortcuts"). :smile:[/quote]
I did the same thing, for k=1-5 n=3355583 and checked all factors with Pari/GP.

Is this the same "friend" who had the radical compression technique?

[quote=Mini-Geek;129024]I did the same thing, for k=1-5 n=3355583 and checked all factors with Pari/GP.[/quote]
I deleted my message, because I thought I put the output into Pari/GP wrong...but on second thought, though, it looks like I did do it correctly. :whoops: Can a mod please bring back my message?

[CODE]? n=3355584;forprime(p=3,1000,if(Mod(2,p)^n+1==0,print(p)))
769
[/CODE]

The Windows version of NewPGen will not let me stop a test with divisor less that 1000 nor log divisors less than 2^32. I challenge jasong and his friends to reproduce their divisor of 2 by NewPGen :lol:

[QUOTE=ewmayer;129013]Yes, Bob is dating himself, but Bob has an admirably reckless disregard for fashion and fads. The rest of us, slaves to hipster trends as we are, probably would prefer more up-to-date jargon such as "Dude, put down the crack pipe!" or even more trendily, the text-message-y "d00d, R U Hi?"[/QUOTE]

Crack gets one high. But quaaludes cause hallucinations similar to acid...

Hmmm.... I might have run into an interesting bug in NewPGen. When I sieved k*b^n+1 form with (b=2,n=3355583,kmin=2,kmax=16), NewPGen declared all candidates as composite, instantly. However, if i give kmin=kmax=2, NewPGen just happily keeps going without finiding any factors!!

@Jasong, Try using the sieve option "b^n+k" with b=2, nmin=nmax=3355584 and k=1. NewPGen will instantly find the factor 769.

[QUOTE=axn1;129029]Hmmm.... I might have run into an interesting bug in NewPGen. When I sieved k*b^n+1 form with (b=2,n=3355583,kmin=2,kmax=16), NewPGen declared all candidates as composite, instantly. However, if i give kmin=kmax=2, NewPGen just happily keeps going without finiding any factors!!
[/QUOTE]

It is a bug only if you not specify "include even k":

[CODE]Base = 2
Include even k's ? (y) : n
n = 3355583
kmin = 2
kmax = 2
Type : k.b^n+1
The output file newout already exists - continue? (y) : y
Are you ready to start sieving ? (y) : y
CPU capabilities: CMOV: Supported. SSE2: Supported.
Using bitmap : allocating 0.0Kb of RAM...
...succeeded
0 candidates
Sieving numbers with 1010132 decimal digits
Initialising sieve...
Done.
02:26:06 Starting sieve (reduced screen output while p < 1 billion)
Stopping...o 33554467 (33.5 million)
02:26:10 Saving results to newout...
02:26:10 ...done.
Output file 'newout' generated, contains 0 k's
[/CODE]

Paul ought to iron this out :smile:

I have emailed him :wink:

[quote=jasong;129019]If you tell NewPGen to sieve k=1 to 5 for the equation k*2^3355583+1, it will say everything has been sieved and all have been found composite, and it will do that in less than a second.[/quote]

[quote=jasong;129019]I'll repeat my challenge. Find a factor for 2^3355584+1 and test it without shortcuts. If my friends(or tolerators, possibly) at Riesel Sieve tell me that they've duplicated the result, then I'll shut up. Otherwise, you should seriously consider showing so-called cranks more respect.[/quote]

Not certain which you want factors for, but I'll assume you mean the second.

The following factors were found via ECM using Prime95.

2^3355584+1: 769*274177*[SIZE=2]961934081
[/SIZE]
Using GMP I then obtained 2^3355584+1 Mod(f) for each factor obtained via GMP. Each resulted in a mod result of 0.

My understanding is that Prime95 uses an FFT computation in the interests of speed, while GMP uses integer math. However I could very easily be incorrect regarding these statements. However both packages are open source and nobody has ever found any errors in the computation methods of either.

Two different methods used to obtain the factors and to test the validity of factors. Both methods open source and reviewed by a large number of people.

I doubt that any conspiracy exists with the goal to ignore potential primes. It appears that 2^3355584+1 not only tests as being a composite, but also has (some) easily identifiable factors.

Was there anything else your friend would like to state, for the record?

[QUOTE=paulunderwood;129030]It is a bug only if you not specify "include even k":
[/QUOTE]

D'oh! Of course. :smile: Still a bug, just not the one I imagined.

comment deleted.

[quote=jasong;129033]bc is running the equation ((2^3355584)+1)/789 right now.

Oops, the file gave out a number that was cut off at the top after it was printed. I want to make sure I'm doing this right, so after I solve one, I can turn around and plug in the answer in the place 789 is above. If 789 is a factor, than switching the numbers should get the result 789.[/quote]

If you're attempting to triple check the factors I found, you may want to use the correct factors. I said

2^3355584+1: [B][U]769[/U][/B]*274177*[SIZE=2]961934081[/SIZE]

[quote=jasong;128958]My friend has told me(approximate quote),"A lot of the stuff that people accept as fact is not true,[/quote]Yup.

A common reason is simple, nondelusional ignorance.

Another common reason is imperfect memory or the imperfections of our human languages.

Example: In a recent post elsewhere in mersenneforum.org I objected to someone's use of "decimate" to mean removing one-tenth of (whatever), because I sincerely thought then that I recalled that "decimate" meant removing [I]nine[/I]-tenths of (whatever), or dividing (whatever) by ten.

Once I actually consulted a dictionary, I discovered that I had been mistaken for several years.

I'm pretty sure I correctly knew what "decimate" meant at some time in the past. Perhaps I became confused because of one of the other meanings of "decimate". Webster's Third New International has "[B]2 a :[/B] to take a tenth from". But later in the entry is "[B]3 :[/B] to destroy a considerable part of [B]:[/B] reduce to the point of almost complete extermination" -- a meaning more in line with the idea of removing 90% rather than just 10%, to me at least.

[quote]so-and-so(note: I'm not telling who or what was mentioned, but it isn't George :) ) intentionally stacked the deck so that they would find the first 10-million digit prime.[/quote]Then there are accidental misunderstandings.

Some prime searches, in order to try to be first to find a 10-million-digit prime, have proceeded nonsequentially, or at least non-exhaustively, through candidates, skipping certain ranges in order to work up to the 10-million-digit region more quickly than if they had worked on every possible sub-10-million-digit candidate first.

There's nothing immoral, unethical, or illegal about that tactic, to me (and many other folks), as long as they carefully document which ranges have been covered and which haven't (which is more a matter of professionalism than ethics or morality).

But I can imagine that some people might have a different opinion as to the morality or ethicality of skipping ranges. Perhaps your friend is one of those, or perhaps has read/heard only a biased description of that tactic given by someone else in that category or else by someone who, for some reason, wants to portray that tactic as "stacking the deck".

(The latter would be more of a deliberately-induced misunderstanding.)

[quote]Because of this, a lot of primes on the top-5000 list are actually composite.[/quote]As has already been pointed out, a simple way to prove that claim would be to produce some examples of top-5000 listings that are actually composite.

Asking your friend to do that, or asking your friend to ask whoever he got his information from to do that, might clarify the matter.

Perhaps your friend does not understand the distinction between probabilistic primality tests and deterministic ones.

[quote]From the way he said it(as I said, it's an approximate quote), it sounds like people have discovered what he discovered in the past(further than you would believe) and it is being suppressed.[/quote]Sounds sort of like an urban legend. See "Urban Legends Reference Pages" at [URL]http://www.snopes.com/[/URL], not for this particular claim, but to see similar patterns in other claims, mathematical or not.

[quote]I don't think my friend is a liar, but there are only two possibilities left, delusional and genius.[/quote]No, you've overlooked additional mundane possibilities such as I've just outlined. (OTOH, you know your friend better than I do!)

[QUOTE=Jay;129034]If you're attempting to triple check the factors I found, you may want to use the correct factors. I said

2^3355584+1: [B][U]769[/U][/B]*274177*[SIZE=2]961934081[/SIZE][/QUOTE]
Okay, scratch the statement I made before this post. All I can say is, WTF?

I attempted division by 789 and got a whole number result. If that isn't a factor, that what the hell happened?

Dividing by a non-factor will result in a non-zero remainder. Dividing by 789 will give you a remainder of 656. Which proves that 789 is not a factor (divisor) of 2^3355584+1. However dividing by 769 does give a remainder of zero, which proves that it is a factor (divisor).

[quote=paulunderwood;129030]It is a bug only if you not specify "include even k":

[code]Base = 2
Include even k's ? (y) : n
n = 3355583
kmin = 2
kmax = 2
Type : k.b^n+1
The output file newout already exists - continue? (y) : y
Are you ready to start sieving ? (y) : y
CPU capabilities: CMOV: Supported. SSE2: Supported.
Using bitmap : allocating 0.0Kb of RAM...
...succeeded
0 candidates
Sieving numbers with 1010132 decimal digits
Initialising sieve...
Done.
02:26:06 Starting sieve (reduced screen output while p < 1 billion)
Stopping...o 33554467 (33.5 million)
02:26:10 Saving results to newout...
02:26:10 ...done.
Output file 'newout' generated, contains 0 k's
[/code]Paul ought to iron this out :smile:

I have emailed him :wink:[/quote]

An interesting bug! I'll take a look - at least it will mean that the very latest version will get out there.

[QUOTE=jasong]


You didn't quote what I said, and I have a bad memory, so I'll have to come back to this later if it starts looking important.
[/QUOTE]


You have failed to answer my question: What do YOU mean by "effective".

[QUOTE=jasong]
My friend claimed
[/QUOTE]

Who is this "friend"? When/where did he/she get his math degree?


[QUOTE=jasong]
Again, you didn't quote me, but my friend claims that NewPGen spits out the number 2^3355584+1 as having a factor of 2, which is clearly impossible.
[/QUOTE]


And you can't imagine that a piece of compute code might have a bug?
Or that the INPUTS might be wrong??? And once again you quote this
soi-dissant "friend". The peculiarities of a piece of code do not define
the underlying mathematics. Or is this too hard for you to understand.

[QUOTE=jasong]
I suggest you consult a life coach on personal etiquette. This has gone beyond sniping in your case, and I'm not simply talking about our encounters.
[/QUOTE]

Others have made the some comments that I have. I notice that you do
not comment on *their* ettiquette. Or is your blaming the *messenger*
a way of avoiding the technical issues? It would seem so.

Jason, I hold you in such utter contempt that it would be hard to find
the proper words to describe it.

[quote=R.D. Silverman;129054]
Jason, I hold you in such utter contempt that it would be hard to find
the proper words to describe it.[/quote]
Come on folks its my 58th birthday today.
I would hesitate to compare Jason's mathematical
prowess with Mally's (what is 0/0?) but surely even
our late lamented Mumbai resident would have blushed at this "comment".:smile:

David

"My friend claimed that Legendre symbols weren't a proven method of determining whether a number was a likely candidate to sieved by a p-value."

They certainly are. I believe what jasong is talking about is the practise - used for fixed k sieves - of not bothering to check to see if a prime p divides any members of the set if it does not pass a number-theoretical test based on the legedre symbol. This is really useful for things like Seventeen or Bust where there are several different k's; it means that you can not bother doing any work at all with some values of p, or you can reduce the amount of work that you have to do.

This is the basics of the technique:

Consider a fixed k sieve, k.2^n+1, with n from n_min to n_max.

We have the next prime, p.

If p divides k.2n+1, then
k.2^n = -1 (mod p), therefore

-k.2^n = 1 (mod p)

For even values of n, this means that -k must be a square mod p.
For odd values of n, this means that -2k must be a square mod p.
So if legendre (-k, p) <>1 and legendre (-2k, p) <> 1, there is no need to test with this value of p.

I think if you check the box for "Verify results" in NewPGen, it will check to see if the factor really divides the candidate, right? And there's a similar option in srsieve, too. Shouldn't that eliminate the bad factors that jasong is worrying about?

[QUOTE=davieddy;129059]Come on folks its my 58th birthday today.

[/QUOTE]


Happy Birthday.

I note that you are a Piscean whilst I, born just a few days later am an Aries. Correspondingly, our natures will be very different.

Richard.

[QUOTE=R.D. Silverman;129054]Jason, I hold you in such utter contempt that it would be hard to find the proper words to describe it.[/QUOTE]
The idea that would have any respect for your opinion at all at this point is laughable. I view you the same way you view Hitler, and that is not an understatement. You have a murderous heart and you will probably be close enough to hear his screams when you reach your true home.

The idea that this Forum is referred to as a math forum is a sick joke. The forums at this site that are either fun or productive are fun because math isn't discussed in them, and when it is, the normal suspects generally aren't aware of it, so things tend to stay civil. The various prime projects are fun because the smart-asses that are so smug about the knowledge don't tend to discuss it in those forums, probably because they aren't there to have a good time, but to degrade people. The factoring forum is tolerable, or not, depending on what the subject matter is. If people come here to learn math, of just about any sort, there is a better than even chance that they will be insulted within a few hours of starting their thread.

For those of you who come here to discover prime numbers, I hope you enjoy your stay. I would encourage you to take specifically mathematical questions to other forums, or use Google.

As far as the unanswered questions are concerned, I say to R.D. Silverman and the other people who have insulted me(with the exception of wblipp. If he distances himself from me on this, I am not hurt. Whatever his opinion of me, I would love to crunch his project in the future, since he generally seems to be a fairly kind individual.) FUCK YOU!!! If you wish to know how my trials go with testing (2^3355584+1)/769, you may inquire at Riesel Sieve Forum in a week or two. I fully expect to discover that 769 DOESN'T divide the number. I believe the only numbers that divide 2^3355584+1 are 1 and 2^3355584+1. It will never show up on the Prime Pages because LLR is flawed, not because of theory or programming, but because Intel chips are flawed. It would also appear that AMD is attempting similar tactics to attempt to get their performance crown back, so applications that require a very high amount of precision are going to be very screwed in the future, though DC projects of that sort already are. For those of you who require proof, I have lost all respect for this forum, so don't really care what people believe. This post is what is called closure.

Goodbye, and may your fish dinners contain bones, and may your bowel movements be bloody, hard, and painful.

[QUOTE=jasong;129143]I believe the only numbers that divide 2^3355584+1 are 1 and 2^3355584+1.[/QUOTE]

Jason,

I gave you three factors in message #22. 769 is a factor of the second one, so it does divide your number.

Do you see that x+1 always divides x[sup]3[/sup]+1?

Do you see that this means (4+1) divides 4[sup]3[/sup]+1?

And 3221+1 divides 3221[sup]3[/sup]+1?

Set x = 2[sup]64*17477[/sup]

Do you see that 2[sup]64*17477[/sup]+1 divides (2[sup]64*17477[/sup])[sup]3[/sup]+1?

Do you see that (2[sup]64*17477[/sup])[sup]3[/sup]+1 = 2[sup]64*17477*3[/sup]+1 ?

Do you see that 2[sup]64*17477*3[/sup]+1 = 2[sup]3355584[/sup]+1?

This same trick works for ANY exponent that has a odd factor.

[quote=jasong;129143]I fully expect to discover that 769 DOESN'T divide the number. I believe the only numbers that divide 2^3355584+1 are 1 and 2^3355584+1.[/quote]

2^3355584+1=(2^1118528+1) x (2^2237056-2^1118528+1)

[QUOTE=Richard Cameron;129080]Happy Birthday.

I note that you are a Piscean whilst I, born just a few days later am an Aries. Correspondingly, our natures will be very different.

Richard.[/QUOTE]

Happy birthday David. I got 46 on 7th...

Luigi

[quote=PaulJobling;129157]2^3355584+1=(2^1118528+1) x (2^2237056-2^1118528+1)[/quote]
I just made Pari/GP output those two things to files and compared them with COMP. Guess what, they're precisely the same...big surprise.

Jasong, you know of a way you can prove or disprove that 769 divides 2^3355584+1? Write it out on paper using a calculator to assist you (unless they're in the conspiracy, too).
Be my guest. Multiply 2 by itself 3,355,584 times then add one (or have the computer do this part if you trust it for that) and manually divide that by 769.
Just don't make a single mistake during any of it, and you'll be fine.

If all the major chip makers are reducing their precision, how do you plan to prove that 2^3355584+1 is prime? With an iPod? Graphing calculator maybe? Have fun waiting years for it to finish...

[QUOTE=jasong;129143]It will never show up on the Prime Pages because LLR is flawed, not because of theory or programming, but because Intel chips are flawed. It would also appear that AMD is attempting similar tactics to attempt to get their performance crown back, so applications that require a very high amount of precision are going to be very screwed in the future, though DC projects of that sort already are.[/QUOTE]

The presumption that LLR (or PRP, Prime95, PFGW) being incorrect just because they run on Intel chips is flawed. What jasong forgets is that LLR can run on any CPU in the x86 family, chips made by both Intel and AMD, from the 386 to the P4 to the Sempron to the Core 2 Duo. Is he saying that all versions of x86 are flawed and have the same flaw? He also forgets that most numbers on the Prime Pages can be verified on non-x86 hardware (although it takes more time). Is he saying that all chips, even non-x86 chips, have a flaw introduced by Intel?

[QUOTE=jasong;129143]For those of you who require proof, I have lost all respect for this forum, so don't really care what people believe. This post is what is called closure.[/QUOTE]

As far as I am concerned, go and go quickly. I don't think many of us will miss you. You had many opportunities to learn from this forum, some in this thread. We cannot help you if you choose to refuse those opportunities. Maybe you should join Ttn and his project...

As a warning to everyone else, I expect his vitriol to carry over to the other forums that he participates in. I've had similar run-ins with him elsewhere for the same reasons that we see in this thread, specifically, he refuses to accept that some people know far more than he does about sieving, factoring, and PRP testing. Although I tend to be a little more civil than Bob, I also tend to be a little more sarcastic and like to point out flaws in logic, which has put me on jasong's and Ttn's *hit lit. Their problem is that they tend to refuse to admit that they are wrong.

[QUOTE=jasong;129143]Goodbye, and may your fish dinners contain bones, and may your bowel movements be bloody, hard, and painful.[/QUOTE]

To jasong: So Long, and Thanks for All the Fish

[QUOTE=jasong;129143]The idea that would have any respect for your opinion at all at this point is laughable. I view you the same way you view Hitler, and that is not an understatement. You have a murderous heart and you will probably be close enough to hear his screams when you reach your true home.

The idea that this Forum is referred to as a math forum is a sick joke. The forums at this site that are either fun or productive are fun because math isn't discussed in them, and when it is, the normal suspects generally aren't aware of it, so things tend to stay civil. The various prime projects are fun because the smart-asses that are so smug about the knowledge don't tend to discuss it in those forums, probably because they aren't there to have a good time, but to degrade people. The factoring forum is tolerable, or not, depending on what the subject matter is. If people come here to learn math, of just about any sort, there is a better than even chance that they will be insulted within a few hours of starting their thread.

For those of you who come here to discover prime numbers, I hope you enjoy your stay. I would encourage you to take specifically mathematical questions to other forums, or use Google.

As far as the unanswered questions are concerned, I say to R.D. Silverman and the other people who have insulted me(with the exception of wblipp. If he distances himself from me on this, I am not hurt. Whatever his opinion of me, I would love to crunch his project in the future, since he generally seems to be a fairly kind individual.) FUCK YOU!!! If you wish to know how my trials go with testing (2^3355584+1)/769, you may inquire at Riesel Sieve Forum in a week or two. I fully expect to discover that 769 DOESN'T divide the number. I believe the only numbers that divide 2^3355584+1 are 1 and 2^3355584+1. It will never show up on the Prime Pages because LLR is flawed, not because of theory or programming, but because Intel chips are flawed. It would also appear that AMD is attempting similar tactics to attempt to get their performance crown back, so applications that require a very high amount of precision are going to be very screwed in the future, though DC projects of that sort already are. For those of you who require proof, I have lost all respect for this forum, so don't really care what people believe. This post is what is called closure.

Goodbye, and may your fish dinners contain bones, and may your bowel movements be bloody, hard, and painful.[/QUOTE]

Mathematics is not for the weak-hearted or the easily upset. Silverman has a point, whether or not you agree with his delivery.

You come in here spouting nonsense. You aren't even aware that it's nonsense. You refuse to learn. You refuse to go read the books that people tell you to read. You get some wild-ass idea (which is fine!) and then ask for information about it, and then when someone tells you where to find more information, you abandon the idea (which is [i]not[/i] fine!). You wanted to tell us "FUCK YOU"? Every time you DON'T read a book you're told to read, you're already saying it loud and clear. Some people have patience or just don't care. Silverman does, and you're too sensitive to look past the abrasion and actually TAKE GOOD ADVICE.

Instead of following through with expert information given to you, you decide instead to hang out with someone who CLEARLY has no clue what the hell is going on, has paranoid delusions and shit-for-math.

Finally, stop using your mental illness as a crutch. EVERYONE on this board knows that your education was cut short because of your mental illness. You mention it almost every third post. GET OVER IT. I have plenty of friends who have mental illness issues, and they do fine in mathematics. Hell, look at John Nash.

Stop apologizing for being an amateur and then getting offended when you get treated like one. Stop apologizing for not knowing the requisite material and GO LEARN THE REQUISITE MATERIAL. You've been repeatedly told where to find it. Yes, it's hard. No, it's not glorious. Sometimes it's very dull, unexciting work. But everyone who helps you has gone through it, and I loathe people who want to abuse the knowledge of others to try and take a shortcut. You have to put in the work.

Tough Love claims another victim...

BTW, who is this "Hilter" fellow jasong seems to dislike so much? Is he a famous mathematician - perhaps a distant name-mangled relative of Hil[i]bert[/i]? Does he have a function space named after him? You know, as in

[i]"Hilter space ... the final frontier..."[/i]

I can see how that kind of math credibility on the late Mr. Hilter's part would make the jasong's of this world intensely resentful.

[QUOTE=jasong;129143]If you wish to know how my trials go with testing (2^3355584+1)/769, you may inquire at Riesel Sieve Forum in a week or two. I fully expect to discover that 769 DOESN'T divide the number.[/QUOTE]

By way of a postscript, allow me to spare the folks here the "suspense" of waiting breathlessly for the results of Jasong's "trials" of his alleged prime:

Question: Does 769 divide (2^3355584+1)?

Answer: Exponent 3355584 = 1100110011001111000000 in base 2. To check divisibility by 769, use the LR exponentiation algorithm to obtain 2^3355584 modulo 769, then add 1 to the result:
[code]
iteration bit x % 769 ("residue")
--------- --- --------------------
0 1 2
1 1 2*x^2 = 8, % 769 = 8
2 0 x^2 = 64, % 769 = 64
3 0 x^2 =4096, % 769 = 251 (from here on just show the modded result)
4 1 2*x^2 % 769 = 655
5 1 2*x^2 % 769 = 615
6 0 x^2 % 769 = 646
7 0 x^2 % 769 = 518
8 1 2*x^2 % 769 = 655
9 1 2*x^2 % 769 = 615
10 0 x^2 % 769 = 646
11 0 x^2 % 769 = 518
12 1 2*x^2 % 769 = 655
13 1 2*x^2 % 769 = 615
14 1 2*x^2 % 769 = 523
15 1 2*x^2 % 769 = 299
16 0 x^2 % 769 = 197
17 0 x^2 % 769 = 359
18 0 x^2 % 769 = 458
19 0 x^2 % 769 = 596
20 0 x^2 % 769 = 707
21 0 x^2 % 769 = 768
[/code]
Add one to get 769, which == 0 modulo 769, hence 769 divides (2^3355584+1). A child could do it - if it weren't a whiny, petulant unwilling to listen and learn, that is.

And Jason, what you "discover" with respect to the above divisibility problem matters not one whit, since the above PROVES that 769 is a divisor. Not "possibly shows," not, "is likely effective", but PROVES - do you even have a clue as to what that means? Wait, don't answer that if it means you coming back to here to waste more of our time and the forum's bandwidth.

[url]http://en.wikipedia.org/wiki/Conspiracy_theory[/url]

[QUOTE=ewmayer;129179]BTW, who is this "Hilter" fellow jasong seems to dislike so much?[/QUOTE]He was a candidate in the North Minehead by-election in the 1970's.

I'm surprised jasong has even heard of him. He (jasong) clearly has a better education than I'd surmised from his postings here.


Paul

<wild speculation>
Considering the original post's emphasis on 10-million digit prime, I am just wondering may be the intended number is F25 = 2^2^25+1 = 2^33554432+1. It looks similar, is over 10m digits, and is at least a non-trivial candidate (except for the fact that it has [URL="http://www.prothsearch.net/fermat.html#Larger"]three known factors[/URL])
</wild speculation>

[QUOTE=xilman;129203]He was a candidate in the North Minehead by-election in the 1970's.[/QUOTE]

Ah yes, it's [url=http://www.humorlinks.com/python/sketches/TheNorthMineheadBye-election.htm]all coming back to me now[/url] - I seem to recall a Green theme to his candidacy - no buses and electronic equipment for the campaign staff, just bicycles and bullhorns. IIRC he was doing surprisingly well in the polls [given that no one could understand what he was saying in his impenetrable German accent] until some bizarre-but-innocent proposal he floated to the effect of every Dutchman deserving a living room was misheard and promptly sound-bited as [i]"Jedem Deutschen sein Lebensraum"[/i], which led to a rather unfortunate comparison with a near-namesake of 40 years earlier being drawn. Poor bloke - he meant well, he just wasn't good at public-image shaping. Of course much of blame for that falls on the shoulders of his feckless campaign coordinator, Ron Vibbentrop.

[i]"Oh well, you'll want the A39 then...no, no, you've got the wrong map there, this is Stalingrad, you want the Ilfracombe and Barnstaple section."[/i]

[QUOTE=ewmayer;129179]
Question: Does 769 divide (2^3355584+1)?

Answer: Exponent 3355584 = 1100110011001111000000 in base 2. To check divisibility by 769, use the LR exponentiation algorithm to obtain 2^3355584 modulo 769, then add 1 to the result:
[code]
iteration bit x % 769 ("residue")
--------- --- --------------------
0 1 2
1 1 2*x^2 = 8, % 769 = 8
2 0 x^2 = 64, % 769 = 64
3 0 x^2 =4096, % 769 = 251 (from here on just show the modded result)
4 1 2*x^2 % 769 = 655
5 1 2*x^2 % 769 = 615
6 0 x^2 % 769 = 646
7 0 x^2 % 769 = 518
8 1 2*x^2 % 769 = 655
9 1 2*x^2 % 769 = 615
10 0 x^2 % 769 = 646
11 0 x^2 % 769 = 518
12 1 2*x^2 % 769 = 655
13 1 2*x^2 % 769 = 615
14 1 2*x^2 % 769 = 523
15 1 2*x^2 % 769 = 299
16 0 x^2 % 769 = 197
17 0 x^2 % 769 = 359
18 0 x^2 % 769 = 458
19 0 x^2 % 769 = 596
20 0 x^2 % 769 = 707
21 0 x^2 % 769 = 768
[/code]
Add one to get 769, which == 0 modulo 769, hence 769 divides (2^3355584+1). A child could do it - if it weren't a whiny, petulant unwilling to listen and learn, that is.
[/QUOTE]

Using Fermat's little theorem:
2^768==1 (mod 769)
So 2^3355584+1 (mod 769) becomes:
2^(768*N+192) +1 (mod 769) for some N
2^(768*N)*2^192+1 (mod 769)
(2^(678))^N*2^192+1 (mod 769)
(1)^N*2^192+1 (mod 769) using Fermat's little theorem
2^192+1 (mod 769)

We know 2^768-1 is factored as (2^384+1)*(2^192+1)*(2^192-1) by recursive use of the difference of two squares: A prime "p=4*n+1" could divide (2^n+1).

192 in binary is 10100010 and could govern a 7-step version of Ernst's algorithm.

Is Pierre at Intel? :no:

[QUOTE=paulunderwood;129299]192 in binary is 10100010 and could govern a 7-step version of Ernst's algorithm[/QUOTE]I thought 192 was 11000000 (0xc0)!

[QUOTE=retina;129302]I thought 192 was 11000000 (0xc0)![/QUOTE]

You are right: I put 162 into pari :redface:

[QUOTE=jasong;128958]The idea that a Fermat prime cannot have odd prime factors in the exponent, is it proven, or just BELIEVED to be effective? If I give a number, like 2^68544+1, can you give me an actual factor with that information, or is it mathematics that makes you believe it has a factor? Are there ANY gaps in the reasoning?[/QUOTE]

This is proven, yes. No gaps in the reasoning.

[QUOTE=jasong;128958]If I give a number, like 2^68544+1, can you give me an actual factor with that information, or is it mathematics that makes you believe it has a factor?[/QUOTE]

769 is a factor, as others have pointed out, as is 91393. It should not be hard for you to write a quick computer program to verify this with nothing but 32-bit integer operations:
[code]n = 1;
for (i = 0; i < 68544; i++)
n = (n * 2) % 769;
n = (n + 1)%769;
print("2^68544+1 is " & n & " mod 769.");[/code]

Similar code would work for other numbers of the form 2^m+n with small prime factors. In particular, m and n should be less than your maximum integer, and the factor less than half that.

For larger m binary exponentiation would be better, but you may not 'trust' such a technique, basic as it is.

[QUOTE=jasong;128958]After that twin prime fiasco with Intel, wouldn't it be better to test numbers with an integer based test after the normal test is run?[/QUOTE]

Probably not, since in many/most cases it would take prohibitively long.

[QUOTE=jasong;128958]Because of this, a lot of primes on the top-5000 list are actually composite.[/QUOTE]

Extraordinary claims require extraordinary evidence. Ask your friend to name one composite on the list (or two hundred, if he's able). I'm extremely skeptical; I'd be surprised if there was even one composite, let alone "a lot".

[QUOTE=jasong;128958]Lastly, is there an integer based prime testing program that would work on an x86 LInux box? If I could get my hands on one and use it, I could establish 100% in my own mind that I wasn't simply being taken for a ride. I don't think my friend is a liar, but there are only two possibilities left, delusional and genius.[/QUOTE]

For the large Mersenne primes, you'd need many months, maybe a year (depending on your computer's speed) using a specialized algorithm. Without a specialized algorithm (but still using floating-point methods) the computer wouldn't finish in your lifetime. With integer-only methods, the calculation might not finish even if you moved the computations to increasingly-fast computers throughout your life.

I don't know about delusional, but I could easily agree that your friend is 'taking your for a ride'.

[QUOTE=R.D. Silverman;128985]As for how many of the top 5000 primes have been tested by purely integer methods, I doubt anyone knows. What difference does it make?
The prior Intel FP bug is now a red herring. The problem has been corrected.
People have thoroughly checked the current IA32 chips for their FP
correctness.[/QUOTE]

Despite a lack of any background or basis on which to draw the conclusion, I think a healthy skepticism of floating-point math is fair. The space is too large to exhaustively test for 64-bit operations. An old personal computer could test all unary 32-bit operations in a fraction of a second. A powerful supercomputer could test all binary 32-bit operations or all unary 64-bit operations in a month. But all binary 64-bit operations... even if you could calculate at an effective rate of 1 THz, and operations were commutative to cut out half the work, a bank of half a billion computers could take the lifetime of the universe to finish (based on the conservative estimate here: [url=http://arxiv.org/abs/hep-th/0510003]Page2005[/url]).

I did read a paper relating to better methods for automated testing of such operations, but it was about getting to the 32x32 and unary 64 verification.

[QUOTE=CRGreathouse;129307]For the large Mersenne primes, you'd need many months, maybe a year (depending on your computer's speed) using a specialized algorithm. Without a specialized algorithm (but still using floating-point methods) the computer wouldn't finish in your lifetime. With integer-only methods, the calculation might not finish even if you moved the computations to increasingly-fast computers throughout your life.[/QUOTE]Huh, the current top prime can be proven with FFT in less than a month on a newish desktop PC. If you shift that to NTT it might be perhaps worst case of 10 times slower so it should take no more than ~1 year.

There is an innate human desire to believe the worst. This is why conspiracy theories abound.

With zero knowledge of facts but given an unfounded rumor that a conspiracy exists, many people will believe it. When shown factual proof that the conspiracy can not be true, they will simply dig in their heels and claim that you've fallen for lies.

The only way to treat a conspiracy theorist is with kind loving care and a pat on the head. While they offer no value to society, they bring so much humor to the world. :smile:

[QUOTE=retina;129308]Huh, the current top prime can be proven with FFT in less than a month on a newish desktop PC. If you shift that to NTT it might be perhaps worst case of 10 times slower so it should take no more than ~1 year.[/QUOTE]

Is it? I take back what I wrote, then. I thought it was months to prove on a typical PC and a few weeks on a verification supercomputer.

[QUOTE=CRGreathouse;129364]Is it? I take back what I wrote, then. I thought it was months to prove on a typical PC and a few weeks on a verification supercomputer.[/QUOTE]A quad core running v25.6 will eat up the current top prime pretty smartly. I've never seen a NTT done on a number that size but I think a 10x performance hit would be the worst one might expect and probably a bit less than 10x if you choose your prime well.

[QUOTE=retina;129365]A quad core running v25.6 will eat up the current top prime pretty smartly. I've never seen a NTT done on a number that size but I think a 10x performance hit would be the worst one might expect and probably a bit less than 10x if you choose your prime well.[/QUOTE]

Well, good to know, thanks.

I guess you can tell I've been applying my cycles to some other computational tasks recently... my information is outdated. :blush:

It has been said that number theory is the only perfect science because it is so rigorous. The proofs are eternal truths. If Number Theroy proofs were only 99% true somebody would point it out very quickly. Mathematicians know what they are talking about. They are not trying to fool anybody - unless they are cranks of course...

[QUOTE=mgb;130742]It has been said that number theory is the only perfect science because it is so rigorous. The proofs are eternal truths. If Number Theroy proofs were only 99% true somebody would point it out very quickly. Mathematicians know what they are talking about. They are not trying to fool anybody - unless they are cranks of course...[/QUOTE]Unless they make errors, which has been known. For instance, Wiles' initial proof of FLT needed patching up after it had been first revealed.

Paul

[quote=CRGreathouse;129364]Is it? I take back what I wrote, then. I thought it was months to prove on a typical PC and a few weeks on a verification supercomputer.[/quote]

on this forum you can occasionally find some guy asking "George, do you need a quick verification (6 days) ?"
(the one I remember was quite some time ago....)
(I won't reveal names...)

[quote=Anonymous;129022]
Using the latest sr1sieve, I found that 2^3355584+1 is divisible by 5. I verified the factor with Pari/GP (which as far as I know uses plain old straight division, with no "shortcuts"). :smile:[/quote]I thought that 2^k+1 is a multiple of 5 iff k=2 (mod 4) - am I wrong?

Okay, I've reread the thread. After being away for a while, and talking to my friend, I decided that I'd stick to the non-math Forums of Mersenne Forum. If I have any math questions, I'm sure there are forums that are more respectful and helpful than this one.

Anyway, I re-read the first 18 posts, and decided that the responses got me a bit over-excited, which confused me. I now agree that 2^3355584+1 is most definitely NOT prime. But that still leaves the problem of the factor of 2. I believe that the bug in NewPGen is that the Verify option should be considered mandatory if someone intends to find ALL primes in a certain range.

I also believe, though I'm not certain, that the use of Legendre symbols, the use that people claim is 100% reliable, causes the obviously incorrect conclusion that 2^3355584+1 is divisible by 2. (assuming I typed the n-value correctly in this case)

[QUOTE=jasong;131749]I now agree that 2^3355584+1 is most definitely NOT prime. [/QUOTE]

It seems like that you dont know the following fomula
a^n+1 = (a+1)(a^(n-1)-a^(n-2)+...+(-1)^(k-1).a^(n-k)+...+(-1)^(n-1))
when n%2==1

a^n-1 = (a-1)(a^(n-1)+a^(n-2)+...+a^(n-k)+...+1)

and from the first fomula can prove if 2^n+1 is a prime, then n=2^i, where i is a integer.