Re: JSH: Understanding quadratic residues result

<snipping due to length, you can read the previous post>

Summary: The algorithm provided by James requires the provision of values
that can only be known if you know the answer. In fact this happens twice
during the algorithm.

That is an interesting assertion. I'm not sure it matters even if
true.

If you're trying to prove that you can do something FAST, like factor,
it's cheating to use knowledge of the factors to choose various magic
numbers to get the factors. It destroys your claim that it's FAST,
since you skipped over a lot of trial-and-error you'd have to do if
you didn't already know the answer.

In other situations, where you can prove that there is an answer
(e.g. let T be an odd composite integer: it's obvious that T has
two nontrivial factors) it may be OK to prove something about the
answer. Just don't assume you know the answer when the purpose
is to prove that there *is* an answer. Otherwise you end up with
a proof like:

To prove: ice cream has no bones.
Assume: ice cream plus one bone has one bone.
Therefore: ice cream has no bones, proof complete.


Incidentally, James, from some of the things you've said, you may
be able to construct a proof that your method will always come up
with an answer (except for 15), something you haven't done yet.
You said it will always work if you end up with a quadratic residue.
Can you prove it? Can you also prove that there always exists a
choice of magic numbers that makes you end up with a quadratic
residue?

This proof might also be able to put a bound on the number of
guesses for magic numbers you have to try before it works, which
might help with a speed proof. Although I'm still not convinced
it is faster than trial division.

.

Relevant Pages

  • Re: Neanderthals
    ... differences in shoulder anatomy by sex. ... "James A. Donald" ... The bones that underlie and support the shoulders ...
    (rec.arts.sf.composition)
  • Re: Will NASA honour Scotty ( James Doohan )
    ... > (Leonard 'Bones' McCoy)? ... > James Doohan's ashes would be on a rocket flight though. ...
    (sci.space.shuttle)
  • Re: Very cheap solar power
    ... Ice cream has no bones. ... 31 Flavors. ... I ordered a BBQ rib sundae and was told "Don't you know ice cream got ...
    (sci.physics)
  • Re: Cursed Excalibur How-to
    ... James wrote: ... got lucky enough to find the bones, ... and if it's not impossible it happens in this game. ... I'd consider the rest of what I found in the bones. ...
    (rec.games.roguelike.nethack)
  • Napiers Bones for other algorithms?
    ... We've been implementing a nice little algorithm to determine the square ... apparently taught to children in up to the '60s as a nice simple way to ... square-root of a number exactly (each iteration providing another digit ... Napier's Bones. ...
    (sci.math.num-analysis)