bernsteinisms.h

Go to the documentation of this file.

// Copyright (C) 2011 CNRS - Ecole Polytechnique - INRIA.
//
// This file is part of TIFA.
//
// TIFA is free software; you can redistribute it and/or modify it under the 
// terms of the GNU Lesser General Public License as published by the Free
// Software Foundation; either version 2.1 of the License, or (at your option)
// any later version.
//
// TIFA is distributed in the hope that it will be useful, but WITHOUT ANY
// WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
// FOR A PARTICULAR PURPOSE.  See the GNU Lesser General Public License for
// more details.
//
// You should have received a copy of the GNU Lesser General Public License
// along with this library; if not, write to the Free Software Foundation,
// Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301 USA.

#if !defined(_TIFA_BERNSTEINISMS_H_)

#define _TIFA_BERNSTEINISMS_H_

#ifdef __cplusplus
extern "C" {
#endif

#include <inttypes.h>
#include "array.h"
#include "x_array_list.h"
#include "hashtable.h"
#include "smooth_filter.h"

//-----------------------------------------------------------------------------
// Ref. "How to find small factors of integers", Daniel J. Bernstein
//       http://cr.yp.to/papers/sf.pdf
//-----------------------------------------------------------------------------

mpz_t* bern_51(uint32_t b, const mpz_t u);

mpz_t* bern_53(uint32_t b, const mpz_t u, const mpz_t x);

uint32_array_t* bern_63(const mpz_t x, const mpz_array_t* const tree);

void bern_71(
    uint32_array_list_t* const decomp_list,
    const mpz_array_t* const to_be_factored,
    const uint32_array_t* const odd_primes
);

//-----------------------------------------------------------------------------
// Ref. "How to find smooth parts of integers", Daniel J. Bernstein
//       http://cr.yp.to/factorization/smoothparts-20040510.pdf
//-----------------------------------------------------------------------------

uint32_t bern_21_rt(
    mpz_array_t* const smooth,
    const mpz_array_t* const xi,
    const mpz_t z
);

uint32_t bern_21(
    mpz_array_t* const smooth,
    const mpz_array_t* const xi,
    const mpz_t z
);

uint32_t bern_21_rt_pairs(
    mpz_array_t* const xi,
    mpz_array_t* const smooth_yi,
    const mpz_array_t* const cand_xi,
    const mpz_array_t* const cand_yi,
    const mpz_t z
);

uint32_t bern_21_pairs(
    mpz_array_t* const xi,
    mpz_array_t* const smooth_yi,
    const mpz_array_t* const cand_xi,
    const mpz_array_t* const cand_yi,
    const mpz_t z
);

uint32_t bern_21_rt_pairs_lp(
    const mpz_t n,
    hashtable_t* const htable,
    mpz_array_t* const xi,
    mpz_array_t* const smooth_yi,
    const mpz_array_t* const cand_xi,
    const mpz_array_t* const cand_yi,
    const mpz_t z
);

uint32_t bern_21_pairs_lp(
    const mpz_t n,
    hashtable_t* const htable,
    mpz_array_t* const xi,
    mpz_array_t* const smooth_yi,
    const mpz_array_t* const cand_xi,
    const mpz_array_t* const cand_yi,
    const mpz_t z
);

uint32_t bern_21_rt_pairs_siqs(
    mpz_array_t* const xi,
    mpz_array_t* const smooth_yi,
    mpz_array_t* const a_for_smooth_gx,
    const mpz_array_t* const cand_xi,
    const mpz_array_t* const cand_yi,
    const mpz_array_t* const cand_a,
    const mpz_t z
);

uint32_t bern_21_rt_pairs_lp_siqs(
    const mpz_t n,
    hashtable_t* const htable,
    mpz_array_t* const xi,
    mpz_array_t* const smooth_yi,
    mpz_array_t* const a_for_smooth_yi,
    const mpz_array_t* const cand_xi,
    const mpz_array_t* const cand_yi,
    const mpz_array_t* const cand_a,
    const mpz_t z
);

uint32_t djb_batch_rt(
    smooth_filter_t* const filter,
    unsigned long int step
);

#ifdef __cplusplus
}
#endif

#endif

---