Opened 12 years ago

Last modified 4 years ago

#6232 new enhancement

Consider CADO-NFS for inclusion

Reported by: malb Owned by: malb
Priority: minor Milestone: sage-wishlist
Component: packages: optional Keywords: linear algebra, factoring, number theory
Cc: zimmerma, leif, wbhart, jpflori Merged in:
Authors: Reviewers:
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Description (last modified by zimmerma)

CADO-NFS is an implementation of the number field sieve:

CADO is sponsored by the French Research Agency (ANR).
It started in 2008 for 3 years. It involves 3 teams: CACAO (INRIA Nancy), TANC (INRIA Saclay), and Gerald Tenenbaum’s team (IECN Nancy). 

Objectives:
 * better understand how the Number Field Sieve works
 * publish a state-of-the art implementation, not to break new
   records, but to routinely factor numbers of 155 digits
 * use that code base to try new ideas and/or new algorithms

http://webloria.loria.fr/~zimmerma/talks/cado.pdf

The Block-Wiedemann in CADO-NFS might be of independent interest.

Change History (11)

comment:1 Changed 11 years ago by malb

  • Report Upstream set to N/A

I vote for closing this ticket, no point in having it around since no motion to actually include it is happening.

comment:2 Changed 9 years ago by zimmerma

We just released version 1.1 of CADO-NFS, see http://cado-nfs.gforge.inria.fr/

Paul

comment:3 Changed 9 years ago by zimmerma

see also #5310: both msieve and cado-nfs implement the number field sieve.

comment:4 Changed 9 years ago by leif

  • Cc leif added

comment:5 Changed 6 years ago by jdemeyer

  • Component changed from packages: standard to packages: optional

comment:6 Changed 6 years ago by zimmerma

  • Cc wbhart added

I use this ticket to report an issue related to CADO-NFS. I'm not sure the problem is due to Sage. I could open a separate ticket if needed.

The issue is the following. Some colleague wrote the following Sage code to call CADO-NFS from Sage:

import subprocess
def my_exec_factor(nbr):
    cmd = ['/tmp/cado-nfs-1.1/factor.sh', str(nbr)]
    process = subprocess.Popen(cmd, stderr=subprocess.STDOUT, stdout=subprocess.PIPE)
    output, unused_err = process.communicate()
    retcode = process.poll()
    if retcode:
        print "Output :"
        print output
        raise subprocess.CalledProcessError(retcode, cmd)
    return output

res=my_exec_factor(90377629292003121684002147101760858109247336549001090677693)

r=[]
for i in res.splitlines()[-6].split(' '):
    r.append(Integer(i))
print r

When used with CADO-NFS 1.1, this code works fine.

However with CADO-NFS 2.1.1 it fails:

sage: %runfile /tmp/garambois.sage
Output :
(debug mode, temporary files will be kept in /tmp/cado.mru0w9AeIM)
Fatal Python error: Py_Initialize: Unable to get the locale encoding
  File "/usr/local/sage-6.0-x86_64-Linux/local/lib/python/encodings/__init__.py", line 123
    raise CodecRegistryError,\
                            ^
SyntaxError: invalid syntax

Current thread 0x00002b81297f1700 (most recent call first):
/tmp/cado-nfs-2.1.1/factor.sh: line 242: 13296 Aborted                 "${TIMEOUT[@]}" $PYTHON $cadofactor "$t/param" N=$n tasks.execpath="$bindir" tasks.threads=$cores tasks.workdir="$t" slaves.hostnames="$hostnames" slaves.nrclients=$slaves slaves.scriptpath="$scriptpath" "$server_address" slaves.basepath="$t/client/" "$@"
FAILED ; data left in /tmp/cado.mru0w9AeIM

---------------------------------------------------------------------------
CalledProcessError                        Traceback (most recent call last)
<ipython-input-1-cf20ddc02bb1> in <module>()
----> 1 get_ipython().magic(u'runfile /tmp/garambois.sage')

/usr/local/sage-6.0-x86_64-Linux/local/lib/python2.7/site-packages/IPython/core/interactiveshell.pyc in magic(self, arg_s)
   2134         magic_name, _, magic_arg_s = arg_s.partition(' ')
   2135         magic_name = magic_name.lstrip(prefilter.ESC_MAGIC)
-> 2136         return self.run_line_magic(magic_name, magic_arg_s)
   2137 
   2138     #-------------------------------------------------------------------------

/usr/local/sage-6.0-x86_64-Linux/local/lib/python2.7/site-packages/IPython/core/interactiveshell.pyc in run_line_magic(self, magic_name, line)
   2060                 args.append(sys._getframe(stack_depth).f_locals)
   2061             with self.builtin_trap:
-> 2062                 result = fn(*args)
   2063             return result
   2064 

/usr/local/sage-6.0-x86_64-Linux/local/lib/python2.7/site-packages/sage/misc/sage_extension.pyc in runfile(self, s)

/usr/local/sage-6.0-x86_64-Linux/local/lib/python2.7/site-packages/IPython/core/magic.pyc in <lambda>(f, *a, **k)
    189     # but it's overkill for just that one bit of state.
    190     def magic_deco(arg):
--> 191         call = lambda f, *a, **k: f(*a, **k)
    192 
    193         if callable(arg):

/usr/local/sage-6.0-x86_64-Linux/local/lib/python2.7/site-packages/sage/misc/sage_extension.pyc in runfile(self, s)
     77         """
     78         from sage.misc.preparser import load_wrap
---> 79         return self.shell.ex(load_wrap(s, attach=False))
     80 
     81     @line_magic

/usr/local/sage-6.0-x86_64-Linux/local/lib/python2.7/site-packages/IPython/core/interactiveshell.pyc in ex(self, cmd)
   2382         """Execute a normal python statement in user namespace."""
   2383         with self.builtin_trap:
-> 2384             exec cmd in self.user_global_ns, self.user_ns
   2385 
   2386     def ev(self, expr):

<string> in <module>()

/usr/local/sage-6.0-x86_64-Linux/local/lib/python2.7/site-packages/sage/misc/preparser.pyc in load(filename, globals, attach)
   1770             # Preparse in memory only for speed.
   1771             exec_file_is(fpath)
-> 1772             exec preparse_file(open(fpath).read()) + "\n" in globals
   1773     elif fpath.endswith('.spyx') or fpath.endswith('.pyx'):
   1774         exec_file_is(fpath)

<string> in <module>()

<string> in my_exec_factor(nbr)

CalledProcessError: Command '['/tmp/cado-nfs-2.1.1/factor.sh', '90377629292003121684002147101760858109247336549001090677693']' returned non-zero exit status 134

My guess is that there is an interaction between the version of Python used by CADO-NFS 2.1.1 (Python 3) and the one used by Sage (Python 2.7). (Note that CADO-NFS 1.1 did not use Python but Perl instead.)

Can anybody reproduce that problem? Any idea how to solve it?

Paul

comment:7 Changed 6 years ago by zimmerma

by the way the above code, if we manage to make it work with recent versions of CADO-NFS, might be useful to factor large integers from within Sage.

Paul

comment:8 Changed 6 years ago by zimmerma

thanks to Alexander Kruppa, the solution is to undefine the environment variables PYTHONHOME and PYTHONPATH:

import subprocess, os
def my_exec_factor(nbr):
    cmd = ['/tmp/cado-nfs-2.1.1/factor.sh', str(nbr)]
    my_env = os.environ
    if my_env.has_key("PYTHONHOME"):
       my_env.pop("PYTHONHOME")
    if my_env.has_key("PYTHONPATH"):
       my_env.pop("PYTHONPATH")
    process = subprocess.Popen(cmd, stderr=subprocess.STDOUT, stdout=subprocess.PIPE, env=my_env)
    output, unused_err = process.communicate()
    retcode = process.poll()
    if retcode:
        print "Output :"
        print output
        raise subprocess.CalledProcessError(retcode, cmd)
    return output

comment:9 Changed 6 years ago by zimmerma

in addition, one should unset PATH:

    if my_env.has_key("PATH"):
       my_env.pop("PATH")

and replace res.splitlines()[-6] by res.splitlines()[-2] for CADO-NFS 2.1.1.

Paul

comment:10 Changed 6 years ago by jpflori

  • Cc jpflori added

comment:11 Changed 4 years ago by zimmerma

  • Description modified (diff)

fixed typo in description (CADO-NSF -> CADO-NFS)

Note: See TracTickets for help on using tickets.