--- In primenumbers@y..., Phil Carmody <fatphil@a...> wrote:
> In other words, given non-square n, what's the size of the smallest
b that is a square-denier (yes, neologism) for n.
>
> Is there a case where the smallest square-denier for n is >sqrt(n)
(done without taking a square root, of course!)
> In Marcel's case the smallest square denier is b=2^2, for reference.
>
Cases of non-square n with smallest square-denier > sqrt(n):
... Young man. At your age, at our age, young man... ... OK, I retract my part retraction too. ... As always, hats off to Marcel. ... Oh good. I've have a...
... b that is a square-denier (yes, neologism) for n. ... (done without taking a square root, of course!) ... Cases of non-square n with smallest square-denier...
... Hehe, I knew I'd be beaten to this. Hmmm, must buy laptop... Incidentally, what algorithm did you use? I'd guess a straight sieve would work (which would...
... would work (which would be blazingly fast)? The CRT method seems to fan out too much to be practical. What range do you think you could practically search...
May I try to summarize what has been found so far on this topic? (for all of us who have a hard time keeping up with you blazingly fast thinkers.) A. We're...
If you read msg 4790, there may be a slight misunderstanding involving the distinction between the quadratic residue concept and the Jacobi symbol used to...
... It appears that my generic sieve can't cope with non-prime bases in its filters. (i.e. the prime power bases). So I'm running at about 5% of my top speed...
... Well, I improved my sieve a bit, and I currently have a run rate of just over 20 million numbers a second, or about 7.5*10^10 / hour. This is on a Pentium...
... Given the choice, I always sieve on my 533MHz alpha. ... I have some crappy overheads that I need to get rid of per block so I've aimed my sieve at my 96K...
... hour. ... I bow before the master. I should go throw my sieve program into a bottomless pit, and study at the FatPhil school of sieving, I guess....
... Note that 4790 had a bit of 2+2=5 logic in it. However, without that post, Jack and I would never have started hunting for the aberrant 5s! ... Absolutely....
... 1) Use CRT as much as possible. (I could go to ~72 then ~130G/s by putting another prime or two in the CRT stage). 2) Saturate the pipelines for each tiny...
OK, I think I understand more now about the Jacobi symbol (after reading more in the Prime Pages Glossary about it). ... You're right. Here's what I found: The...
... Don't be fooled, any composite based tests are not Jacobi symbols. They are the 'intersection' of two Legendres. If one fails, the composite fails. ... ...
The only reference I saw addressing this question is in Cohen's "A Course in Computational Algebraic Number Theory", which states that a number n is a square...
jfribrg@...
Jan 19, 2002 5:00 pm
The square detcection algorithm is in Cohen, section 1.7.2, page 39-40. Ron ... From: jfribrg@... <jfribrg@...> To: primenumbers@yahoogroups.com...
Ronald Hallam
ronhallam@...
Jan 19, 2002 7:29 pm
... Absolutely. I put a smallish challenge to a guy on sci.math who came up with the same observation. Finding ones which are hard to factor was hard! I...
... Prime powers under 200 and a cherry on top! Someone beat me to the cherry, alas: http://www.ams.org/journal-getitem?pii=S0025-5718-96-00678-3 Oh dear -...
... The values that Cohen uses are 64, 63, 65, and 11. 99% of non-squares fail ones of these tests. After this, an integer square root must be calculated. ...
... Does he say why? It's obvious really: 64 is 'instant' But why not do 64 bits simultaniously, rather than just 6? - see my 4-clock-tick no-lookup-table...
... Because the rejection ratios are greatest in that order, as you say. Cohen suggests that it might be better to do it all in one go (save for the mod 64, ...
... Yeah, but wouldn't you rather 'divide' it by 16777215 = 0xFFFFFF? Take 3 words (p,q,r) from memory and partition the bytes as follows into 4 24-bit...
... I saw someone else (I think it was the GMP guys) recommend the idea for using 4 separate registers rahter than one massive 96-bit value requiring carries...
... As I said in http://groups.yahoo.com/group/primenumbers/message/4855 when I first lambasted Henri's arbitrary choice of 11, <<< Therefore the number of...
... This was a typo I guess. 45045 was what I meant. Regards, Paul. __________________________________________________ Virus checked by MessageLabs Virus...