Re: N=prime or composite ?

On 25 Jun., 09:26, Vincenzo Librandi <vincenzo.librandw...@xxxxxxxx>
wrote:
Vincenzo Librandi wrote:
in order to find the limitation of n we do not
have to take advantage of the dividing ones of
N but single N, a, b.

hagman wrote:
I don't know what you mean here.

If M=factors, then N is composite.

Do you agree that (N+1-2a)/2 is bigger
than N/(2M) - sqrt(N) + M/2 ?

Yes, but for
N=prime number, then factor is 1.

N=43 then for your formula:
43/2-7+1/2=15

.... with M=1. But by merely stating that N is odd,
you have effectively stated that M=3, i.e. N you
have tested that N is not divisible by any number <3.
Thus:
43/6 - sqrt(43) + 3/2 = 2.19
It is therefore enough to try n=0, n=1, n=2:
We have a = ceil(sqrt(N)) = 7, b = a^2-N = 6
n=0: n^2+2an+b = 0+0+6 = 6
n=1: 1 + 14 + 6 = 21
n=2: 4 + 28 + 6 = 38
No square found => 43 is prime

Same with N=45, a=7, b=4:
n=0: n^2+2an+b = 0+0+4 = 4 is square
=> 45 is composite

Same with n=39, a=7, b=10:
n=0: n^2+2an+b = 0+0+10 = 10
n=1: 1 + 14 + 10 = 25 is square
=> 39 is composite.


For my formula:
(43+1-14)/2=15

Your primality proof would be:
n=0: n^2+2an+b = 0+0+6 = 6
n=1: 1 + 14 + 6 = 21
n=2: 4 + 28 + 6 = 38
n=3: 9 + 42 + 6 = 57
....
n=14: 196 + 196 + 6 = 398
No square found => prime


How we can tie M with N, a, b?

Regards,
Vincenzo Librandi

Getting M involved was just a method of improving the
bounds by doing trial division with small primes first.
For example, you originally started merely with the
assumption that N is odd, i.e. you have checked beforehand
that N is not divisible by 2.
Therefore, without further checks, my formula with M=3 applies.
Most primality tests and factoring methods start by trial
division with the first few small primes; I gave an example
where I tried division up to including 7, whereas it is
customary to try all primes below 1000000, say.

.

Relevant Pages

  • Re: A challenge involving two large semi prime composites.
    ... the smallest prime in each composite is a consecutive ... triangle number that it is the index of? ... no primes between p and r and no primes between q and s ... tri number counterpart. ...
    (sci.math)
  • Re: Methods that count primes without counting primes or referringto them...
    ... simple fact that instead of finding the primes and counting them, ... a bunch of primes that can be easily counted. ... the values of m3give the positions of the composite numbers whithin s1 ... of course, there is really no need to store the matrix elements of m1, m2 ...
    (sci.math)
  • Re: Factoring paper is wrong
    ... Most numbers are composite with more than two factors, ... Perhaps he started with two primes and ... bits trial division was comparable in speed or better than other methods. ... winter, cwi, kruislaan 413, 1098 sj amsterdam, nederland, +31205924131 ...
    (sci.math)
  • Re: Factoring paper is wrong
    ... Most numbers are composite with more than two factors, ... Perhaps he started with two primes and ... bits trial division was comparable in speed or better than other methods. ... winter, cwi, kruislaan 413, 1098 sj amsterdam, nederland, +31205924131 ...
    (sci.physics)
  • Re: Factoring paper is wrong
    ... Most numbers are composite with more than two factors, ... Perhaps he started with two primes and ... bits trial division was comparable in speed or better than other methods. ... winter, cwi, kruislaan 413, 1098 sj amsterdam, nederland, +31205924131 ...
    (sci.crypt)