question: decidability for quadratic residues modulo a composite

[Mr. P-1]

Originally Posted by LaurV

Yo can't guess. You need a precise answer. I will give you an example:

Assume p is a prime and m=Mp its correspondent mersenne number. Let x=2^((p-1)/2)+1. If neither x nor -x is quadratic residue, then Mp is composite. I don't know if this result is known, but if it is not known, it is because nobody bothered to compute it, because the proof is really elementary calculus. So, how "guessing" will help you in this case? If you have Joe's hat, he could tell you at once if x or -x are residues. If none of them is, then you don't need to run a LL test. If one of them turn out to be a residue (in this example only one can be residue, because Mp is 4k+3 and -1 is never a quadratic residue, so only one of z and -z can be qr, for any z), then in that case you still don't know anything about primality of Mp.

The question you posed earlier was whether a single use of Joe's hat could be useful to factor N, not merely to determine whether N was composite. Clearly a single use of a yes/no oracle could substantially assist in the computation (if not decide outright) a yes/no question. It can do no more than half the work necessary to perform a factorisation.

[LaurV]

Well, thanks everyone! You are right! I am now starting to understand what you guys are trying to tell me. After doping myself with some theory too, I see the empty side of the glass, too. It's the magnitude of these numbers what cheats me every time... these numbers are huuuuuge...

[R.D. Silverman]

Originally Posted by ccorn

That's two questions already. And this setup is not about determining factors.

Edit: OK, it's just one question because only one Jacobi symbol can be +1, and the other one need not be asked.
Yet, this is is not about determining factors.

Anyway, seeing that the idea makes you read about exclusion moduli (and perhaps even Lehmer's bicycle chain sieve), I'll stop grunting and let you follow your thoughts.

When the computer museum was in Boston (in the 80's) Lehmer's
photoelectric sieve was stored in a storage area. It was not on display,
although it had been on display when the museum was in Marlborough
(maintained by DEC). I had asked the museum staff about the device.
They of course were clueless. They had a LOT of historical computer
hardware in storage and knew very little about most of it: It's importance,
the technology etc. All they knew was how to show the public how to
run the various computer GAMES that were out front on display. Of course
all of the items that were of historical importance were not on display.
The only hardware of real historical importance that was on display was
the Whirlwind.

I managed to convince the staff to allow me to access (and try out!)
the photoelectric sieve. It was lacking a rubber belt to connect the
motor to the gears, and it was lacking a photo-detector. I borrowed
a small laser to act as a photo source and a photomultiplier to act as a
detector from my employer at the time: MITRE. I hooked the thing up
and everyone was flabbergasted (me included) that the thing actually
ran. The staff asked about all of the toothpicks that were inserted into
the holes in the wheels. I tried to explain that plugging these holes was
how the device was programmed, but of course the staff was clueless
about arithmetic and my explanation about excluding certain modular
classes went right over their head.

Now, I understand the museum is out at Berkeley. I ask if anyone has
seen it in its present incarnation. I also ask what kind of museum has
someone totally clueless about the museum content as its curator?

[Christenson]

RDS brings up an interesting point: If the computer museum people don't know what a mechanical calculator is, would an archaeologist recognise an electronic one if he found it in a pyramid?

[Uncwilly]

Originally Posted by Christenson

RDS brings up an interesting point: If the computer museum people don't know what a mechanical calculator is, would an archaeologist recognise an electronic one if he found it in a pyramid?

What if they find a preserved Mark I biological computer? Would they recognized it as such?

[LaurV]

@RDS: That is a really fascinating story! Thank you for sharing it.
(no joke, I love reading about these history stuff, almost more than I am enjoying reading about math :D, and I also learned a new English word: flabbergasted)
I imagine the faces of that guys...

[GP2]

I found this old thread, where it seems that LaurV was already kind of thinking along lines similar to the new Jacobi check, which was described just last month (literally discovered by "error") and is now incorporated in Prime95 v29.3.

I wonder, though, how recently the fast algorithm for computing Jacobi symbols was discovered.

[LaurV]

Well, what I was trying to do at the time, was to "improve" the LL test
Unfortunately, with no success...

Subjects on mersenneforum have the bad habit that are re-told every few years, people come and go, discussions are forgotten, then a new guy comes and starts a thread and the things are explained again and again.

The Jacobi "test" is not new, it is known for ages, just that it was not worth computationally till recently.