integer factorization - 2025 ACF Fall

Tossup

Hendrik Lenstra developed an algorithm for performing this task using elliptic curves, (10[2]-5[2])whose two-stage (-5[3])variant is analogous (-5[1])to one (10[1]-5[1])named after Pollard. (-5[2])Dixon’s method for performing this task (-5[1])forms (10[1])the basis of an algorithm (-5[1])for performing this task (10[1])using continued fractions. In 1994, a quantum algorithm (10[1])for performing (-5[2])this (10[1])task (10[3]-5[1])in (10[1])polynomial (10[1]-5[2])time (10[1])was (10[1])developed (10[2]-5[2])by Peter (10[1])Shor. (10[8]-5[8])RSA (10[1]-5[1])encryption (10[3]-5[2])relies (-5[1])on (10[1])the (-5[1])difficulty (10[2]-5[1])of (10[1])performing (10[4])this (10[1]-5[1])task (10[4]-5[1])for (10[2])large (10[1]-5[1])integers. (10[6]0[1]-5[2])For (10[1])an integer (10[1])n, (-5[1])a brute force (10[1])method (10[2])for performing this task checks (-5[1])all the integers (10[1]-5[1])from 1 (10[1])to the square root (10[1])of n. (-5[2])For 10 points, name this task that decomposes an integer into a product (10[4])of smaller integers. (10[3])■END■ (10[32]0[5])

ANSWER: integer factorization [or word forms like factoring; accept prime factorization]

<Editors, Other Science>

= Average correct buzz position

Back to tossups

Buzzes

Player	Team	Opponent	Position	Value
Rishi Mathur	Claremont B	UCLA F	11	-5
Nate Brown	CWRU C	Pittsburgh	11	10
Skand Parvatikar	Arizona State B	Alberta A	11	10
Will Hoover	RIT A	Cornell B	11	-5
Chris Chang	USC A	UC Santa Barbara	13	-5
Eric Morshed	Johns Hopkins	George Mason A	13	-5
Daniel Chen	Emory A	Mississippi State A	13	-5
Dustin Sanders	Chicago B	Chicago A	16	-5
Vijay Hans	Berkeley Boss Bandit	Berkeley Skeleton King	18	-5
Daniel Lu	Washington Pink	Arizona State A	18	10
Sidarth Erat	MIT A	Boston University B	21	-5
Jake Markus	Dartmouth B	Williams C	21	-5
Taman Truong	USC B	UCSD B	27	-5
Will Huang	Wisconsin A	Minnesota	28	10
Anthony Gagliano	McGill A	Ottawa A	33	-5
Brody Johnson	Louisville B	Ohio State C	37	10
Thomas Brittain	McMaster C	Toronto A	45	10
Ethan Tran	UCLA C	Claremont A	47	-5
Taran Knutson	Michigan A	CWRU B	47	-5
Kevin Hendargo	UCSD A	UCLA B	48	10
Adrian Li	Berkeley Archer Queen	Stanford B	49	10
Denali Tran-Le	McGill B	Ottawa B	49	10
Johnathan Ahdout	Princeton	George Mason B	49	10
Owen Linder	Binghamton A	ESF	49	-5
Darren Kellis	Vanderbilt A	Georgia Tech C	50	10
Peyton Legg	UCF A	Florida Tech B	51	-5
Zaid Asif	NYU A	Maryland A	51	10
Shivam Saxena	Georgia Tech F	Tennessee Tech	51	-5
Matthew Wozniak	Michigan B	Louisville A	52	10
Beckett Pursey	Purdue B	Purdue D	53	10
Daniel Craig	Rutgers B	Lehigh B	54	-5
Jiping Fang	Illinois Blue	Iowa B	54	10
Francis Dinh	Illinois Canada	Rose-Hulman A	54	10
Harrison Greenlee	Washington State	Alberta B	54	-5
Daniel Huang	Georgia Tech D	Auburn A	56	10
Ty Brennan	Berkeley Mighty Miner	Berkeley Little Prince	57	10
Tyler Dang	UCLA A	UC Irvine	57	-5
Tianyi Zheng	UCSD B	USC B	57	10
Sicheng Jiang	Toronto H	Guelph A	57	-5
Dawson Teu	Waterloo A	Toronto B	57	10
Nina Chen	Waterloo B	Toronto D	57	10
Nicholas Nguyen	Florida B	Florida State A	57	-5
Liam Rojas	Virginia A	Liberty B	57	10
Trenton Burgess	Indiana A	Illinois Champaign	57	10
James Horsley	Iowa State	Macalester	57	-5
Steven Su	Harvard	Boston College A	57	10
Eames Weeks	Brown A	Boston University A	57	10
Nathaniel Martin	Brandeis Bach	Tufts C	57	-5
Suyog Vibhuti	Washington Steelhead	Washington Coho	57	-5
Jerry Lin	Vanderbilt B	Auburn B	57	-5
Aaron Wang	Cornell A	Rochester	57	-5
Aarnav Vyas	Illinois Orange	Purdue A	58	-5
Zach Majorowicz	St. Thomas	Michigan Tech	58	10
Valerie Brown	Carleton B	Ottawa D	59	10
Ryan Liu	Ohio State D	Michigan D	59	10
Leonard Castine	Penn	Rutgers A	59	-5
Aryan Malhotra	Rutgers C	George Mason C	59	10
Andrew Wilson	Montevallo	Sewanne	59	-5
Max Kurzman	UNC D	NCSU A	60	-5
Reed Sexton	Michigan C	Ohio State B	61	10
Justin Sato	Stanford A	UCSC	62	-5
Brendan Bridle	Queen's A	Toronto G	63	10
Ben Spirtas	Maryland C	Columbia B	63	10
Isaiah Schmid	Binghamton B	Binghamton C	63	-5
Nameer Qadir	Toronto C	Brock A	64	10
Jason Thieu	Michigan State A	Ohio State A	65	10
Samuel Li	William & Mary A	JMU B	65	10
Abbott Sherwin	NCSU A	UNC D	65	10
Shaya Farahmand	Georgia Tech B	Auburn C	65	10
Anthony Xu	Amherst A	Boston College B	66	10
Samarth Prajapati	Georgia Tech E	South Carolina A	66	-5
Ana Torres	McGill C	Ottawa C	67	10
Jason Lee	Rutgers A	Penn	67	10
Alex Dzurick	William Woods University A	WashU Grolars	67	10
Wesley Yu	British Columbia A	British Columbia B	67	10
Martin Brandenburg	Georgia A	Clemson C	67	-5
Ryan Gomes	Florida Tech A	South Florida A	68	10
Nathan Woolery	Louisville C	Michigan State C	68	10
Sam Kung	UNC C	UNC A	69	-5
George Matsumura	Washington Chum	Washington Masu	69	10
Scarlet Rutter	Claremont A	UCLA C	70	10
Nikola Wu	UCLA D	Claremont C	70	10
Platon Gorokhov	Toronto E	McMaster A	70	10
June Miller	Florida A	ERAU Daytona A	70	10
Owen Banks	Duke A	Liberty A	70	10
Andrew Wu	Columbia A	Rutgers D	70	-5
Salil Jain	Williams B	Dartmouth C	70	-5
Taiki Takahashi	Dartmouth C	Williams B	70	0
John Shelley	Clemson B	Chipola College	70	10
Gannon Rice	Clemson A	Vanderbilt C	71	10
Judah Friedman	UConn A	Brandeis Beethoven	73	10
Alan Zhang	British Columbia C	Boise State	74	-5
Vivian Lu	Wisconsin C	Wisconsin B	77	10
Pace Klein	CWRU B	Michigan A	78	10
Reid Eichberg	Tufts B	Southern Connecticut State University A	78	10
Marissa Statos	Illinois Urbana	Indiana B	83	-5
Michael Xu	McMaster B	Toronto I	86	10
Elliott Gomes	Dartmouth A	Brown B	86	-5
Fern Fang	VCU A	JMU A	88	10
Andres Lorenzo	RIT B	Cornell C	92	10
Samuel Zheng	Toronto F	Waterloo C	94	-5
Theodor Martin	WashU Grizzlers	Iowa A	94	-5
Rohan Soni	UCLA F	Claremont B	107	10
William Erwin	William & Mary B	Liberty C	107	10
Nikhil Nair	Boston University B	MIT A	107	10
Jacky Li	MIT B	Vermont A	107	10
Saswat Sasha Tripathi	Chicago A	Chicago B	110	10
Atreya Mallanna	Brown B	Dartmouth A	110	10
Anya Srinivasan	Washington Atlantic	Washington Chinook	110	10
Brandom Pham	Berkeley Skeleton King	Berkeley Boss Bandit	111	10
Lorie Au-Yeung	UCSC	Stanford A	111	10
Advai Srinivasan	UC Irvine	UCLA A	111	10
Winston Zuo	UC Santa Barbara	USC A	111	10
Rebecca Li	Ottawa A	McGill A	111	10
Dylan Steptoe	Guelph A	Toronto H	111	10
Lucas Hall	Waterloo C	Toronto F	111	10
Juan Landaeta	Florida State A	Florida B	111	10
Miles Phillips	Florida Tech B	UCF A	111	10
Bonham Buchannon	Louisville D	WVU B	111	10
Will Jones	Michigan State D	WVU A	111	0
Chase Moss	WVU A	Michigan State D	111	0
Cheyenne Hewitt	Tusculum A	NCSU B	111	0
Parker Travis	NCSU B	Tusculum A	111	0
Nick Smemoe	UNC A	UNC C	111	10
Vivian Adolph	UNC B	William & Mary C	111	10
Nicholas Decker	George Mason A	Johns Hopkins	111	10
Nicholas Ryan	Lehigh B	Rutgers B	111	10
Alex Wong	Rutgers D	Columbia A	111	10
Nico Lotto	Vassar B	Vassar A	111	10
Matthew Westley	Purdue A	Illinois Orange	111	10
Grace Early	Iowa A	WashU Grizzlers	111	10
Anneke Stracks	Macalester	Iowa State	111	10
Devon Kumar	Tufts C	Brandeis Bach	111	10
Akif Ismail	Williams C	Dartmouth B	111	10
Alice Ton Nu	Washington Coho	Washington Steelhead	111	10
Luke Simon	Alberta B	Washington State	111	10
Jackson McDonald	Alabama A	Tennessee B	111	10
Coy Mier	Auburn B	Vanderbilt B	111	10
Jacie Bradley	Clemson C	Georgia A	111	10
Nelson Adams-Riley	Sewanne	Montevallo	111	0
Trey Lewis	South Carolina A	Georgia Tech E	111	10
Daniel Slater	Tennessee Tech	Georgia Tech F	111	10
Gregory Stone	ESF	Binghamton A	111	10
Eli O'Sick Johnson	Binghamton C	Binghamton B	111	10
Aidan Keenan	Rochester	Cornell A	111	10
Gabriel Nell	Cornell B	RIT A	111	10

Summary

Tournament	Edition	TUH	Conv. %	Neg %	Average Buzz
Northern California	US	4	100%	50%	82.00
Southern California	US	7	100%	71%	82.00
Eastern Canada (1)	US	4	100%	25%	71.50
Eastern Canada (2)	US	9	100%	22%	73.78
Florida	US	4	100%	50%	90.00
Great Lakes	US	10	90%	10%	60.22
Lower Mid-Atlantic	US	9	89%	22%	84.25
Upper Mid-Atlantic	US	9	100%	44%	81.44
Midwest	US	9	89%	44%	77.13
North	US	4	100%	25%	68.50
Northeast	US	11	91%	45%	87.70
Pacific	US	8	88%	38%	71.00
Southeast	US	12	83%	50%	86.70
Upstate NY	US	5	100%	80%	107.20