<commit_before>/*
 * mp_composite.c
 * Copyright (C) 2002-2010 <NAME>. All rights reserved.
 *
 * $Id$
 */

#include "mp.h"
#include "mp_defs.h"
#include <stdlib.h>

/* Knuth 4.5.4P: use a variant of the Miller-Rabin probabilistic procedure to
 * test the integer N for compositeness. It will never incorrectly identify a
 * prime as composite, but it may incorrectly identify a composite as prime.
 * For a given round there is a worst-case probability 1/4 that this
 * algorithm guesses wrong; thus for N rounds it guesses wrong with worst-case
 * probability (1/4)^N. With typical input the chances of wrong guess are far
 * more minute. It usually makes sense to first test N for divisibility by
 * small primes using mp_sieve() before calling this function.
 *
 * Return true if N is composite, otherwise false if N is "probably" prime. */
bool
mp_composite(const mp_digit *n, mp_size nsize, unsigned rounds)
{
	MP_NORMALIZE(n, nsize);
	if (!nsize)				/* Call 0 prime. */
		return false;
	if ((n[0] & 1) == 0) {	/* Even N. */
		if (nsize == 1 && n[0] == 2)
			return false;	/* Call 2 prime. */
		return true;
	}
	if (rounds == 0)		/* Nuthin' doin' */
		return true;

	/* Find K and Q such that N = (2^K) * Q + 1, Q odd.
	 * Assumes that it is safe to modify N. */
	mp_digit *q = (mp_digit *)n;
	--*q; /* Can't underflow: N odd. */
	const unsigned k = mp_odd_shift(n, nsize);
	++*q;
	unsigned j = k / MP_DIGIT_BITS;
	const mp_size qsize = nsize - j;
	MP_TMP_COPY(q, n + j, qsize);
	if ((j = k % MP_DIGIT_BITS) != 0) {
		mp_digit cy;
		cy = mp_rshifti(q, qsize, j);
		ASSERT(cy == 1);	/* This is the trailing odd bit. */
	}

	mp_digit *y;
	MP_TMP_ALLOC(y, nsize * 3); /* x will store y^2 */
	mp_digit *x = y + nsize;
	for (unsigned r = 0; r < rounds; r++) {
		/* Generate X so 1 < X < N */
		mp_digit xsize = nsize - (rand() % nsize);<commit_msg>Make use of improved ASSERT macro.<commit_after>/*
 * mp_composite.c
 * Copyright (C) 2002-2010 <NAME>. All rights reserved.
 *
 * $Id$
 */

#include "mp.h"
#include "mp_defs.h"
#include <stdlib.h>

/* Knuth 4.5.4P: use a variant of the Miller-Rabin probabilistic procedure to
 * test the integer N for compositeness. It will never incorrectly identify a
 * prime as composite, but it may incorrectly identify a composite as prime.
 * For a given round there is a worst-case probability 1/4 that this
 * algorithm guesses wrong; thus for N rounds it guesses wrong with worst-case
 * probability (1/4)^N. With typical input the chances of wrong guess are far
 * more minute. It usually makes sense to first test N for divisibility by
 * small primes using mp_sieve() before calling this function.
 *
 * Return true if N is composite, otherwise false if N is "probably" prime. */
bool
mp_composite(const mp_digit *n, mp_size nsize, unsigned rounds)
{
	MP_NORMALIZE(n, nsize);
	if (!nsize)				/* Call 0 prime. */
		return false;
	if ((n[0] & 1) == 0) {	/* Even N. */
		if (nsize == 1 && n[0] == 2)
			return false;	/* Call 2 prime. */
		return true;
	}
	if (rounds == 0)		/* Nuthin' doin' */
		return true;

	/* Find K and Q such that N = (2^K) * Q + 1, Q odd.
	 * Assumes that it is safe to modify N. */
	mp_digit *q = (mp_digit *)n;
	--*q; /* Can't underflow: N odd. */
	const unsigned k = mp_odd_shift(n, nsize);
	++*q;
	unsigned j = k / MP_DIGIT_BITS;
	const mp_size qsize = nsize - j;
	MP_TMP_COPY(q, n + j, qsize);
	if ((j = k % MP_DIGIT_BITS) != 0) {
		ASSERT(mp_rshifti(q, qsize, j) == 1); /* Trailing odd bit. */
	}

	mp_digit *y;
	MP_TMP_ALLOC(y, nsize * 3); /* x will store y^2 */
	mp_digit *x = y + nsize;
	for (unsigned r = 0; r < rounds; r++) {
		/* Generate X so 1 < X < N */
		mp_digit xsize = nsize - (rand() % nsize);
{'fraction_non_alphanumeric': 0.1358326541700625, 'fraction_numerical': 0.017386579733767997, 'mean_word_length': 3.1139664804469276, 'pattern_counts': {'":': 0, '<': 13, '<?xml version=': 0, '>': 7, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '1259789', 'n_tokens_mistral': 1440, 'n_tokens_neox': 1330, 'n_words': 519}