# yafudocumentation

YAFU documentation

The contents of docfile.txt (the help menu). Some of this could be wildly inaccurate.

[help]

YAFU Version 1.09

-------------

Introduction:

-------------

YAFU is a interactive mathematical environment, similar to

MATLAB, pari/gp, or bc. You write expressions on the command line,

and it will interpret and evaluate them. Results can be assigned

to variables, and variables can be used in expressions. Use 'quit'

or 'exit' to exit the application.

You can also call yafu from the OS command line, either by providing

an argument to yafu like this:

yafu "2+2"

or

yafu "siqs(rsa(200))"

Or by redirecting input from somewhere else:

echo "2+2" | yafu

yafu < in.txt

The use of quotes around the expressions may or may not be necessary

depending on the OS. All expressions supported in the interactive

environment are supported in this way.

In addition, when providing arguments to yafu you can specify

flags to change program behavior. Supported flags in v1.07 are:

-B1pm1 <num> B1 bound in the pm1 method

-B1pp1 <num> B1 bound in the pp1 method

-B1ecm <num> B1 bound in the ECM method

-rhomax <num> max iterations in the rho method

-B2pm1 <num> B2 bound in the pm1 method

-B2pp1 <num> B2 bound in the pp1 method

-B2ecm <num> B2 bound in the ECM method

-qssave <name> Name of the siqs savefile to use in this session

-siqsR <num> Stop after finding num relations in siqs

-siqsT <num> Stop after num seconds in siqs

-logfile <name> Name of the logfile to use in this session

-seed <num> 32 bit number for use in seeding the RNG

-batchfile <name> Name of batchfile to use in command line job

-sigma <num> Input to ECM's sigma parameter. Limited to 32 bits.

-session <name> Use name instead of the default session.log

These flags are ignored when redirecting input to yafu.

------------

Batchfiles

------------

New in version 1.07. A command line driver job can take as input a batchfile

using the -batchfile flag. This batchfile can contain any valid YAFU expression

on each line of the file. Optionally, an expression can be supplied on the command

line in the usual manner. In this case the expressions are substituted into the input

expression in place of the special character @ in the input expression.

For example, if you had a file called in.bat containing 10 numbers to be factored,

you could do:

% yafu "factor(@)" -batchfile in.bat

from the command line.

------------

Expressions:

------------

An expression is any (nested) series of functions and/or operators.

Any amount of nesting is possible, so long as the expression is

less than 2048 characters. White space can be used anywhere - it is

removed prior to processing. Expressions must be proper infix notation,

for example -1(7*8) will not work but -1*(7*8) will.

------

Bases:

------

YAFU can handle input/output in several different bases, specified

by the IBASE and OBASE reserved words. Recognized bases include

(for the moment) hexadecimal and decimal. Binary and Octal as

well as arbitrary bases are on the agenda. Once IBASE is set to

a base, all other input is interpreted in that base. Likewise once

OBASE is set, all output appears in that representation.

This behavior can be overridden on input by using 0x before a number

to indicate hexadecimal, or 0d for decimal.

All hexadecimal alphabetic characters must be entered in ALL CAPS.

----------

Operators:

----------

Valid operators include the standard +,-,*,/,%,^, as well as ! for

factorial, # for primorial, >> for binary right shift and <<

for binary left shift. Left and right parentheses can also be used

for grouping.

----------

Functions:

----------

Functions all take the form 'funcname(args)', where funcname is the

function's name and args is some number of comma delimited arguments.

Issuing the command 'help funcname' will bring up more detailed help

on a particular function. Some functions support a variable number

of arguments, with a default defined for the optional arguments. See

the individual functions documentation for more info.

The following are all the supported functions:

utility factoring arithmetic

------------------------------------------------------------------------------------------

rsa factor shift

size siqs nroot

primes mpqs modexp

nextprime qs sqrt

rand squfof lg2

randb pm1 log

pp1 ln

rho gcd

trial jacobi

ecm modinv

fib

luc

llt

----------

Variables:

----------

Variable names can be any combination of lower case alphanumeric

characters including _ and `, but the first character must be

in {a-z} or _. Variable names also cannot be the same as certain

reserved words.

---------------

Reserved Words:

---------------

Some words are reserved by the application and most can be altered

by the user to impact the program execution. They are typically

in all caps. Some examples include:

POLLARD_STG1_MAX - controls the upper bound of p-1 stage 1 factoring

POLLARD_STG2_MAX - controls the upper bound of p-1 stage 2 factoring

WILL_STG1_MAX - controls the upper bound of p+1 stage 1 factoring

WILL_STG2_MAX - controls the upper bound of p+1 stage 2 factoring

ECM_STG1_MAX - controls the upper bound of ECM stage 1 factoring

ECM_STG2_MAX - controls the upper bound of ECM stage 2 factoring

BRENT_MAX_IT - controls the maximum number of iterations in pollard rho

QS_DUMP_CUTOFF - controls the cutoff over which siqs automatically saves

the state of the factorization upon completion

NUM_WITNESSES - the number of witnesses to use in rabin-miller prp tests

IBASE - controls the input numeric base

OBASE - controls the output numeric base

[siqs]

usage: siqs(expression)

description:

the siqs factoring method. uses the single large prime variation, small prime variation,

bucket sieving, and too many other optimizations to mention. post-

processing courtesy of Jason Papadopoulos's msieve block Lanczos implementation.

Useful for inputs < 105 digits. Above that, parameter settings utilizing the double

large prime variation have not been tested at all and most likely are increasingly bad.

For inputs above a configurable size (using QS_DUMP_CUTOFF), will dump

all relations upon completion of sieving, or upon recieving an abort signal (ctrl-c)

QS_DUMP_CUTOFF specifies the factor base size above which the dump is

performed. The default is 2048. Every run of siqs overwrites the save file. If siqs

detects the input is the same as the savefile input, the run is automatically restarted.

The savefile is siqs.dat, and should appear in the same directory as the executable.

For large jobs, the savefile is written as the factorization progress, so the dump

at the end is not necessary. Resuming in this case works exactly the same.

command line flags effecting siqs:

-qssave <name> Name of the siqs savefile to use in this session

-siqsR <num> Stop after finding num relations in siqs

-siqsT <num> Stop after num seconds in siqs

[mpqs]

usage: mpqs(expression)

description:

the mpqs factoring method. uses the single large prime variation, and automatically

switches in the small prime variation depending on the size of the input. post-

processing uses a block gaussian solver and is useful only for moderately

sized inputs.

[qs]

usage: qs(expression)

description:

the qs factoring method. uses the single large prime variation. uses a block gaussian

routine for post processing. limited to 16000 blocks of sieving, due to 32 bit

constraints. As such, is only useful up to about 50 digits, and is far slower than other

qs implementations. However, it will work for inputs as small as about 12 digits, and

is extremely fast in that case.

[factor]

usage: factor(expression)

description:

combines a variety of routines to (hopefully) optimally factor an arbitrary input.

[pm1]

usage: pm1(expression)

description:

Pollard's p-1 factoring method, implementing stage 1 and the enhanced standard

stage 2 continuation with prime pairing. Stage 1 bound is configurable using

the POLLARD_STG1_MAX parameter. The default is 100000. Stage 2 bound is also

configurable using the POLLARD_STG2_MAX parameter. The default is 5000000.

p-1 is resumable in both stage 1 and stage 2. every time it runs, it saves the state after

stage 1 and after stage 2. The save files are re-written every time, similar to the siqs

save file. If pm1 detects that the number in a savefile is the same as the input, it will

automatically resume the run. Stage 2 is checked first, then stage 1.

The savefiles are pm1_stg1_save.dat, and pm1_stg2_save.dat, and should appear

in the same directory as the executable.

command line flags effecting pm1:

-B1pm1 <num> B1 bound in the pm1 method

-B2pm1 <num> B2 bound in the pm1 method

[ecm]

usage: ecm(expression1,[expression2])

description:

The elliptic curve factoring method, implementing stage 1 with PRAC and the enhanced

standard stage 2 continuation with prime pairing (Crandall and Pomerance's 2 muls per

prime version). The first argument should be the number to factor and the second

should be the number of curves to run at the current ECM_STG* bounds. If no

expression2 is given, the default behavior is 1 curve at the current ECM_STG* bounds.

The stage 1 bound is configurable using the ECM_STG1_MAX parameter.

The default is 11000. Stage 2 bound is also configurable using the

ECM_STG2_MAX parameter. The default is 1100000. Currently it is not resumable.

command line flags effecting ecm:

-B1ecm <num> B1 bound in the ECM method

-B2ecm <num> B2 bound in the ECM method

[pp1]

usage: pp1(expression)

description:

Williams's p+1 factoring method, implementing stage 1 and the enhanced standard

stage 2 continuation with prime pairing. Stage 1 bound is configurable using

the WILL_STG1_MAX parameter. The default is 20000. Stage 2 bound is also

configurable using the WILL_STG2_MAX parameter. The default is 1000000.

p+1 is resumable in both stage 1 and stage 2. every time it runs, it saves the state after

stage 1 and after stage 2. The save files are re-written every time, similar to the siqs

save file. If pp1 detects that the number in a savefile is the same as the input, it will

automatically resume the run. Stage 2 is checked first, then stage 1.

The savefiles are pp1_stg1_save.dat, and pp1_stg2_save.dat, and should appear

in the same directory as the executable.

command line flags effecting pp1:

-B1pp1 <num> B1 bound in the pp1 method

-B2pp1 <num> B2 bound in the pp1 method

[rho]

usage: rho(expression)

description:

Pollard's rho method, with Brent's improvement. The maximum number of iterations to

perform is configurable using the BRENT_MAX_IT parameter.

command line flags effecting rho:

-rhomax <num> max iterations in the rho method

[trial]

usage: trial(expression1,[expression2])

description:

trial division of the result of expression1 to a bound specified by the result of

the optional expression2. All primes less than the bound are divided into the input.

If no expression2 is provided, the default value is 10000.

[squfof]

usage: squfof(expression)

description:

Shanks's square form factorization method, using multipliers. Upper bound of the input

is set to 62 bits.

[gcd]

usage: gcd(expression,expression)

description:

greatest common divisor of two inputs, using the Lehmer/Euclid method.

[jacobi]

usage: jacobi(expression,expression)

description:

jacobi symbol of two inputs p/q

[isprime]

usage: isprime(expression)

description:

uses trial division followed by the rabin-miller probabalistic primalty

test to determine probable-primalty. The number of witnesses in the rabin-miller test

is configurable using the NUM_WITNESSES parameter. The default is 20.

[fib]

usage: fib(expression)

description:

computes the nth fibonacci number

[luc]

usage: luc(expression)

description:

computes the nth lucas number

[modinv]

usage: modinv(expression1,expression2)

description:

computes the modular inverse of one number with respect to another

[lg2]

usage: lg2(expression)

description:

the binary log

[log]

usage: log(expression)

description:

the base 10 log

[ln]

usage: ln(expression)

description:

the natural log

[modexp]

usage: modexp(expression1,expression2,expression3)

description:

modular exponentiation: a^b%n

[sqrt]

usage: sqrt(expression)

description:

sqrt using newton's method

[nroot]

usage: nroot(expression1,expression2)

description:

nth root using newton's method. The result of expression2 is the nth root to take of

the result of expression1.

[shift]

usage: shift(expression1,expression2)

description:

binary left or right shift by result of expression2

[hex2dec]

usage: hex2dec(expression)

description:

converts from hexadecimal to decimal representation

[dec2hex]

usage: dec2hex(expression)

description:

converts from decimal to hexadecimal representation

[size]

usage: size(expression)

description:

size of a number, digits and bits

[set]

usage: set(reserved word,expression)

description:

set a global parameter (reserved word)

[rsa]

usage: rsa(expression)

description:

form a difficult to factor number of a specified bit size

[rand]

usage: rand(expression)

description:

form a random number with a specified number of digits

[primes]

usage: primes(expression1,expression2,expression3)

description:

print or count the primes in a range between the first two parameters.

The third parameter is 1 if the range is to only be counted or 0 if printed to

screen. It could take a very long time to print if the range is large.

[nextprime]

usage: nextprime(expression1,[expression2])

description:

find the next prime after a specified number. If it evaluates to zero,

the next prime is smaller than the given number. Else the next prime is larger than the

specified number. If no expression2 is given, the default is the next bigger prime

(as if a non-zero input were given).

[llt]

usage: llt(expression)

description:

start the lucas lehmer test on the number 2^expression - 1. A small amount of trial

division is first performed, after determining that the expression is prime.

Multiplication is N^2, so this is pretty slow for expression evaluating to greater than

10000 or so.

[end]