/* * mersenne - perform a primality test of 2^p-1, for prime p>1 * * Copyright (C) 1999  David I. Bell and Landon Curt Noll * * Primary author:  David I. Bell * * Calc is open software; you can redistribute it and/or modify it under * the terms of the version 2.1 of the GNU Lesser General Public License * as published by the Free Software Foundation. * * Calc 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. * * A copy of version 2.1 of the GNU Lesser General Public License is * distributed with calc under the filename COPYING-LGPL.  You should have * received a copy with calc; if not, write to Free Software Foundation, Inc. * 59 Temple Place, Suite 330, Boston, MA  02111-1307, USA. * * @(#) $Revision: 29.2 $ * @(#) $Id: mersenne.cal,v 29.2 2000/06/07 14:02:25 chongo Exp $ * @(#) $Source: /usr/local/src/cmd/calc/cal/RCS/mersenne.cal,v $ * * Under source code control:	1991/05/22 21:56:36 * File existed as early as:	1991 * * Share and enjoy!  :-)	http://www.isthe.com/chongo/tech/comp/calc/ *//* * NOTE: See lucas.cal for a more general routine. */define mersenne(p){	local u, i, p_mask;	/* firewall */	if (! isint(p))		quit "p is not an integer";	/* two is a special case */	if (p == 2)		return 1;	/* if p is not prime, then 2^p-1 is not prime */	if (! ptest(p,1))		return 0;	/* lltest: u(i+1) = u(i)^2 - 2 mod 2^p-1 */	u = 4;	for (i = 2; i < p; ++i) {		u = hnrmod(u^2 - 2, 1, p, -1);	}	/* 2^p-1 is prime iff u(p) = 0 mod 2^p-1 */	return (u == 0);}