Direction of
International Relations (DRI)
INRIA
Program
"Associate Teams"
Events:
I. DEFINITION
ASSOCIATE TEAM

ANC

selection 
2008 

French Coordinator

Foreign Coordinator

Name, Surname 
Zimmermann, Paul 
Brent, Richard 
Position 
Research Director 
ARC Federation Fellow 
Institute 
INRIA 
ANU, Mathematical Sciences Institute 
Postal Address 
615 rue du jardin botanique, 54600 VillerslèsNancy 
Canberra, ACT 0200, Australia 
URL 
http://www.loria.fr/~zimmerma/ 
http://wwwmaths.anu.edu.au/~brent/ 
Phone 
+33 (0)3 83 59 30 41 
(612) 6125 3873 
Fax 
+33 (0)3 83 27 83 19 
(612) 6125 5549 
Email 
zimmerma {at} loria [dot] fr 
Richard [dot] Brent {at} maths [dot] anu [dot] edu [dot] au 
The proposal in brief
Title of the collaboration (in
english and french):Algorithms, Numbers, Computers (Algorithmes, Nombres, Ordinateurs)

Description :
We propose to join the research efforts of the Computational Mathematics group
at ANU (Australian National University, Canberra, Australia) with those
of the CACAO team from the ``Centre de Recherche INRIA NancyGrand Est''
(Nancy, France) into an INRIA associate
team called ANC (Algorithms, Numbers, Computers).
We wish to extend in such a way
a longterm and successful cooperation between Richard
Brent and Paul Zimmermann to all members of
both teams, in particular young researchers.
The support of the ANC associate team will allow to reinforce that
cooperation, especially in the following common scientific projects:
Smooth Triangular Numbers (Størmer's Problem),
Efficient FiniteField Arithmetic,
Fast evaluation of trigonometric functions,
and Modern Computer Arithmetic. 
Presentation of the
Associate Team
1. Presentation of the foreign coordinator
Richard Brent did his Master of Science and his PhD at Stanford University,
in 1970 and 1971.
He was appointed Foundation Professor of Computer Science at the
Australian National University in 1978.
In March 1998 he became the Statutory Professor of Computing Science in the
University of Oxford.
In March 2005 he took up a 5year position as ARC Federation Fellow in the
Mathematical Sciences Institute and the Research School of Information
Sciences and Engineering at the Australian National University.
He is also a Chief Investigator in the ARC Centre of Excellence for
Mathematics and Statistics of Complex Systems (MASCOS) and head of the
Computational Mathematics group in the Mathematical Sciences Institute at ANU
(more details).
2. History
of the collaboration


2.2. Between INRIA
and ANU:
To our best knowledge, there are two common projects between INRIA and
ANU, and one existing associate team with an Australian partner:
 a CNRS PICS project between the LAGADIC projectteam (Rennes),
ANU (Robert Mahony) and CSIRO in Brisbane (Peter Corke and Jonathan
Roberts), which started in 2006, on
visual servocontrol of unmanned aerial vehicles;
 a international Marie Curie project between the S4 projectteam (Rennes)
and ANU (Sylvie Thiébaux), on Formal methods for multi agents systems
(ends in 2007);
 the associate team Internet Probing
between the TREC projectteam (Rocquencourt)
and the University of Melbourne (Darryl Veitch), which started in 2007;
See also the
Australia page of INRIA's DRI (in french).
3. Impact
: Indicate to what extent, in your own opinion, this
associate team would have an important impact:
 3.1. on the existing collaboration with your
partner
:
Since the return of Richard Brent to Australia in 2005, funding regular
visits is more expensive.
Our aim is to secure our strong collaboration in the future, and to
extend it to all researchers of the Computational Mathematics and CACAO groups, in particular
young researchers (PhD students, postdocs).
 3.2. on the collaboration with other INRIA
projectteams:
we expect the visits of the Australian partners
will interest other INRIA projectteams of the Sym B theme, in
particular ALGO and TANC
 3.3. on the collaboration with other research
teams from the foreign institution
: some common interests on Fast Fourier Transform and Block
Algorithms are shared with the group of
Markus Hegland
(ANU, Mathematical Sciences Institute);
on combinatorial algorithms and asymptotic
combinatorics, some discussions might happen with
Brendan McKay
(ANU, Computer Science Department)
4. Miscellaneous:
any other useful information.
II. PREVISIONS for 2008
Work Plan
(see Section 3 of the auxiliary document for more details)
 Initial contact between the participants
The main objective for 2008 will
be that the participants meet each other. Indeed, so far only the two
coordinators know (part of) the participants of the other team.
We expect several discussions will follow, some research directions will
emerge from the subjects outlined below, and most probably new ideas will
come up.
 Smooth Triangular Numbers (Størmer's Problem)
The main goal here is the multipleprecision computation of logarithms of
integers.
This is related to an algorithm designed by Lehmer to solve
Størmer's Problem (find consecutive integers n and n+1 that are
simultaneously smooth).
We aim to follow a new approach, suggested by Baker's theory of linear
forms.
This would initially address the fundamental question: can this approach
provide a practical alternative to the "Pelldriven" method of
Størmer/Lehmer?
 Efficient FiniteField Arithmetic
Since 2006, P. Gaudry and E. Thomé started to develop
a new library (MPFQ) for the arithmetic over finite fields.
During R. Brent's visit in Nancy in May 2007, some new algorithms were found
for the basecase multiplication of binary polynomials.
In 20072008,
we will write a paper explaining those new algorithms, together with some
variants of ToomCook's algorithm in that case.
In the medium term, we expect that several discussions will happen with
Gaudry, Thomé and Arndt about efficient bitoperations, around the
MPFQ library and the online book Algorithms for programmers from
J. Arndt.
 Fast Evaluation of Trigonometric Functions
The efficient evaluation of trigonometric functions (sin, cos, tan)
is a key problem for developers of arbitrary precision libraries like
MPFR.
Since the Many Digits competition, several discussions arose between the
team members.
We plan to analyze in details several algorithms, which means comparing their
asymptotic complexity, their range of usage (both in terms of precision
and of input domain), and implementing them carefully in the MPFR library
to compare them experimentally.
 Book Modern Computer Arithmetic
The main goal of this book (in preparation) is not only to describe the
best algorithms at highlevel, but really to work out the nasty details that
make the difference between a rough description and a detailed
pseudocode that can
be readily implemented by a programmer.
In 2008, we plan to make a full pass on Chapter 1 (Integer Arithmetic)
to check coherence between the different notations
and algorithms, and to complete its ``Notes and further references'' section.
Chapter 2 (Modular Arithmetic and Finite Fields): we want to add several
important
algorithms which are still missing, and to complete the ``Exercises'' and
``Notes and further references'' sections need.
In all the above themes, some output is expected, either as cowritten
scientific publications, and/or by codeveloped software tools.
Planned Budget for
2008
1. Cofunding
 Does this cooperation already benefit from INRIA support,
or from the foreign partner institution, or from a thirdparty (European
project, NSF, ...)?
No, so far our visits were supported by the budget of the SPACES and
CACAO projectteams on the Nancy side.
 In case your proposal is supported, do you expect a symmetric support from
the foreign partner institution?
Yes, the visits of Richard Brent to Nancy (as past visits already were)
will be supported by the Australian Research Council (ARC) grant.
ESTIMATE OF
COFUNDINGS 
Institute

Amount

ARC (Australian Research Council) 
3100 Euros 








Total

3100 Euros 
2. Exchanges
(see Section 3 and 4 of the auxiliary document for more details)
ESTIMATE OF EXPENSES

Amount (in Euros) 

Number 
Accomodation 
Travel 
Total 
Senior Researcher 
3 
4500 
4800 
9300 
Postdoc 
2 
4800 
3200 
8000 
PhD student 
1 
2400 
1600 
4000 
Student 




Other (detail) :

2 
500 
400 
1000 
Total 
7 
12300 
10000 
22300 



cofunding total 
3100 

Amount "Associate
Team" expected

19200 Euros for 2008 
Remarks or observations:
 The above amounts represent real costs, based on our experience
with previous visits. In particular, they assume the planes tickets
are bought several months in advance. See more details in the
auxiliary document,
Section 4.
 The "Other" line corresponds to the invitation of Arjen Lenstra and
Thorsten Kleinjung in Nancy, to organize a miniworkshop on Recent Advances
in Integer Factorization
© INRIA  mise à jour le 28/08/2007  translated P. Zimmermann 08/10/2007