f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers/*
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers * mpprime.c
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers *
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers * Utilities for finding and working with prime and pseudo-prime
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers * integers
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers *
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers * ***** BEGIN LICENSE BLOCK *****
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers * Version: MPL 1.1/GPL 2.0/LGPL 2.1
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers *
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers * The contents of this file are subject to the Mozilla Public License Version
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers * 1.1 (the "License"); you may not use this file except in compliance with
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers * the License. You may obtain a copy of the License at
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers * http://www.mozilla.org/MPL/
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers *
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers * Software distributed under the License is distributed on an "AS IS" basis,
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers * for the specific language governing rights and limitations under the
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers * License.
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers *
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers * The Original Code is the MPI Arbitrary Precision Integer Arithmetic library.
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers *
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers * The Initial Developer of the Original Code is
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers * Michael J. Fromberger.
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers * Portions created by the Initial Developer are Copyright (C) 1997
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers * the Initial Developer. All Rights Reserved.
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers *
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers * Contributor(s):
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers * Netscape Communications Corporation
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers *
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers * Alternatively, the contents of this file may be used under the terms of
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers * either the GNU General Public License Version 2 or later (the "GPL"), or
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers * the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers * in which case the provisions of the GPL or the LGPL are applicable instead
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers * of those above. If you wish to allow use of your version of this file only
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers * under the terms of either the GPL or the LGPL, and not to allow others to
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers * use your version of this file under the terms of the MPL, indicate your
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers * decision by deleting the provisions above and replace them with the notice
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers * and other provisions required by the GPL or the LGPL. If you do not delete
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers * the provisions above, a recipient may use your version of this file under
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers * the terms of any one of the MPL, the GPL or the LGPL.
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers *
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers * ***** END LICENSE BLOCK ***** */
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers/*
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers * Copyright 2007 Sun Microsystems, Inc. All rights reserved.
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers * Use is subject to license terms.
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers *
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers * Sun elects to use this software under the MPL license.
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers */
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers#pragma ident "%Z%%M% %I% %E% SMI"
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers#include "mpi-priv.h"
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers#include "mpprime.h"
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers#include "mplogic.h"
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers#ifndef _KERNEL
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers#include <stdlib.h>
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers#include <string.h>
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers#else
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers#include <sys/random.h>
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers#endif
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers#define SMALL_TABLE 0 /* determines size of hard-wired prime table */
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers#ifndef _KERNEL
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers#define RANDOM() rand()
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers#else
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers#define RANDOM() foo_rand()
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowersstatic int
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowersfoo_rand()
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers{
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers int r;
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers random_get_pseudo_bytes((uchar_t *)&r, sizeof (r));
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers return (r);
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers}
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers#endif
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers/*
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers mpp_random(a)
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers Assigns a random value to a. This value is generated using the
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers standard C library's rand() function, so it should not be used for
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers cryptographic purposes, but it should be fine for primality testing,
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers since all we really care about there is good statistical properties.
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers As many digits as a currently has are filled with random digits.
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers */
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowersmp_err mpp_random(mp_int *a)
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers{
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers mp_digit next = 0;
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers unsigned int ix, jx;
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers ARGCHK(a != NULL, MP_BADARG);
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers for(ix = 0; ix < USED(a); ix++) {
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers for(jx = 0; jx < sizeof(mp_digit); jx++) {
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers next = (next << CHAR_BIT) | (RANDOM() & UCHAR_MAX);
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers }
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers DIGIT(a, ix) = next;
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers }
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers return MP_OKAY;
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers} /* end mpp_random() */
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers/* }}} */
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers/* {{{ mpp_random_size(a, prec) */
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowersmp_err mpp_random_size(mp_int *a, mp_size prec)
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers{
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers mp_err res;
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers ARGCHK(a != NULL && prec > 0, MP_BADARG);
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers if((res = s_mp_pad(a, prec)) != MP_OKAY)
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers return res;
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers return mpp_random(a);
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers} /* end mpp_random_size() */