One line factor

[Bill Hart]

Here is the one line factoring algorithm in Pari:

h(x)=;for(i=1,1000000000,if(issquare(ceil(sqrt(i*x))^2%x),print1("
",gcd(x,floor(ceil(sqrt(i*x))-sqrt((ceil(sqrt(i*x))^2)%x))))))

Try h(nextprime(10^19)*nextprime(10^21)). It won't keep you waiting.

Here is a link to a half completed paper on the algorithm:

http://sage.math.washington.edu/home/wbhart/onelinefactor.pdf

I don't know if this could make a project for someone, to look at this
algorithm. I think I've looked pretty hard at it, so there probably
wouldn't be much to do, unless you came up with a really clever idea.

Bill.

[William Stein]

Here's a little challenge. Can you implement the "one line factoring"
algorithm in one line of *Python* code?

Adding this algorithm to Sage could be a go project, if it is super
well documented, optimized, etc.

William

[Bill Hart]

You may find you have to up the pari precision to make this work:

\p1000

or something like that.

Bill.

[Tom]

The following seem to work as advertised. Note, you'll want to
from math import sqrt, ceil
before this because Maxima turns an "instant" computation into a
sluggish 2-3 seconds on my laptop

def ReadableOneLineFactor(n,N):
R = Zmod(n)
for i in xrange(1,N):
s = int(ceil(sqrt(n*i)))
m = R(s*s)
sq = is_square(m,True)
if sq[0]:
t = sq[1]
return GCD(n,s-t)

#This was my first idea to recycle computations.
def UnreadableOneLineFactor(n,N):
return (x for x in ((lambda n,i: (lambda n,i,(u,v): GCD(n,u-v) if
v is not None else None)(n,i,(lambda s,n: (s,is_square(Zmod(n)
(s*s),True)[1]))(int(ceil(sqrt(n*i))),n)))(n,i) for i in xrange(1,N))
if x is not None).next()


#This is a much more pythonic way of doing things -- list
comprehension all the way!
#note, I've added line breaks for readability, and this features a
check that I've found
#a nontrivial factor.
def OneLineFactor(n,N):
return (d for d in
(GCD(n,s-t) for s,t in
((s,is_square(Zmod(n)(s^2),True)[1]) for s in
(int(ceil(sqrt(n*i))) for i in xrange(1,N))
) if t is not None
) if d not in [1,n]
).next()



On Apr 10, 9:36 pm, William Stein <wst...@gmail.com> wrote:

[Tom]

[William Stein]

Yep, that works fine. Nice!

You can just use math.ceil and math.sqrt above to avoid having to
import them, since "import math" is done by default in sage.all.
I've attached a screenshot showing OneLineFactor really working in a
single line. I think it is far more impressive to write a 1-line
program in Python than in PARI, and you've shown Bill Hart's name for
this algorithm is fully justified.

-- William