text:
Indus River

The Indus is a transboundary river of Asia and a trans-Himalayan river of South and Central Asia. The 3120 km river rises in mountain springs northeast of Mount Kailash in Western Tibet, flows northwest through the disputed region of Kashmir, bends sharply to the left after the Nanga Parbat massif, and flows south-by-southwest through Pakistan, before emptying into the Arabian Sea near the port city of Karachi.

The river has a total drainage area of circa 1120000 km2. Its estimated annual flow is around 243 km3, making it one of the 50 largest rivers in the world in terms of average annual flow. Its left-bank tributary in Ladakh is the Zanskar River, and its left-bank tributary in the plains is the Panjnad River which is formed by the successive confluences of the five Punjab rivers, namely the Chenab, Jhelum, Ravi, Beas, and Sutlej rivers. Its principal right-bank tributaries are the Shyok, Gilgit, Kabul, Kurram, and Gomal rivers. Beginning in a mountain spring and fed with glaciers and rivers in the Himalayan, Karakoram, and Hindu Kush ranges, the river supports the ecosystems of temperate forests, plains, and arid countryside.

The northern part of the Indus Valley, with its tributaries, forms the Punjab region of South Asia, while the lower course of the river ends in a large delta in the southern Sindh province of Pakistan. The river has historically been important to many cultures of the region. The 3rd millennium BC saw the rise of Indus Valley Civilisation, a major urban civilization of the Bronze Age. During the 2nd millennium BC, the Punjab region was mentioned in the Rigveda hymns as Sapta Sindhu and in the Avesta religious texts as Hapta Həndu (both terms meaning "seven rivers"). Early historical kingdoms that arose in the Indus Valley include Gandhāra, and the Ror dynasty of Sauvīra. The Indus River came into the knowledge of the Western world early in the classical period, when King Darius of Persia sent his Greek subject Scylax of Caryanda to explore the river, c. 515 BC.

Etymology and names
This river was known to the ancient Indians in Sanskrit as Sindhu and to the Persians as Hindu/Həndu which was regarded by both of them as "the border river". The variation between the two names is explained by the Old Iranian sound change *s → h, which occurred between 850 and 600 BC according to Asko Parpola. From the Persian Achaemenid Empire, the name passed to the Greeks as Indós (Ἰνδός). It was adopted by the Romans as Indus. The name India is derived from Indus.

The Ladakhis and Tibetans call the river Senge Tsangpo (སེང་གེ་གཙང་པོ།), Baltis call it Gemtsuh and Tsuh-Fo, Pashtuns call it Nilab, Sher Darya and Abbasin, while Sindhis call it Sindhu, Mehran, Purali and Samundar.

The modern name in Urdu and Hindi is Sindh (, सिंध), a semi-learned borrowing from Sanskrit.

Description

The Indus River provides key water resources for Pakistan's economy – especially the breadbasket of Punjab province, which accounts for most of the nation's agricultural production, and Sindh. The word Punjab means "land of five rivers" and the five rivers are Jhelum, Chenab, Ravi, Beas and Sutlej, all of which finally flow into the Indus. The Indus also supports many heavy industries and provides the main supply of potable water in Pakistan.

The total length of the river varies in different sources. The length used in this article is 3,180 km, taken from the Himalayan Climate and Water Atlas (2015). Historically, the 1909 The Imperial Gazetteer of India gave it as "just over 1,800 miles". A shorter figure of 2,880 km has been widely used in modern sources, as has the one of 3,180 km. The modern Encyclopedia Britannica was originally published in 1999 with the shorter measurement, but was updated in 2015 to use the longer measurement. Both lengths are commonly found in modern publications; in some cases, both measurements can be found within the same work. An extended figure of circa 3,600 km was announced by a Chinese research group in 2011, based on a comprehensive remeasurement from satellite imagery, and a ground expedition to identify an alternative source point, but detailed analysis has not yet been published.

The ultimate source of the Indus is in Tibet, but there is some debate about the exact source. The traditional source of the river is the Sênggê Kanbab (Sênggê Zangbo) or "Lion's Mouth", a perennial spring not far from the sacred Mount Kailash, marked by a long low line of Tibetan chortens. There are several other tributaries nearby, which may form a longer stream than Sênggê Kanbab, but unlike the Sênggê Kanbab, are all dependent on snowmelt. The Zanskar River, which flows into the Indus in Ladakh, has a greater volume of water than the Indus itself before that point. An alternative reckoning begins the river around 300 km further upstream, at the confluence of the Sênggê Zangbo and Gar Tsangpo rivers, which drain the Nganglong Kangri and Gangdise Shan (Gang Rinpoche, Mt. Kailash) mountain ranges. The 2011 remeasurement suggested the source was a small lake northeast of Mount Kailash, rather than either of the two points previously used.

The Indus then flows northwest through Ladakh (Indian-administered Kashmir) and Baltistan and Gilgit (Pakistan-administered Kashmir), just south of the Karakoram range. The Shyok, Shigar and Gilgit rivers carry glacial waters into the main river. It gradually bends to the south and descends into the Punjab plains at Kalabagh, Pakistan. The Indus passes gigantic gorges 4500 - 5200 m deep near the Nanga Parbat massif. It flows swiftly across Hazara and is dammed at the Tarbela Reservoir. The Kabul River joins it near Attock. The remainder of its route to the sea is in the plains of the Punjab and Sindh, where the flow of the river becomes slow and highly braided. It is joined by the Panjnad at Mithankot. Beyond this confluence, the river, at one time, was named the Satnad River (sat = "seven", nadī = "river"), as the river now carried the waters of the Kabul River, the Indus River and the five Punjab rivers. Passing by Jamshoro, it ends in a large delta to the South of Thatta in the Sindh province of Pakistan.

The Indus is one of the few rivers in the world to exhibit a tidal bore. The Indus system is largely fed by the snow and glaciers of the Himalayas, Karakoram and the Hindu Kush ranges. The flow of the river is also determined by the seasons – it diminishes greatly in the winter while flooding its banks in the monsoon months from July to September. There is also evidence of a steady shift in the course of the river since prehistoric times – it deviated westwards from flowing into the Rann of Kutch and adjoining Banni grasslands after the 1816 earthquake. , Indus water flows in to the Rann of Kutch during its floods breaching flood banks.

History

The major cities of the Indus Valley Civilisation, such as Harappa and Mohenjo-daro, date back to around 3300 BC, and represent some of the largest human habitations of the ancient world. The Indus Valley Civilisation extended from across northeast Afghanistan to Pakistan and northwest India, with an upward reach from east of the Jhelum River to Ropar on the upper Sutlej. The coastal settlements extended from Sutkagan Dor at the Pakistan-Iran border to Kutch in modern Gujarat, India. There is an Indus site on the Amu Darya at Shortughai in northern Afghanistan, and the Indus site Alamgirpur at the Hindon River is located only 28 km from Delhi. As of now, over 1,052 cities and settlements have been found, mainly in the general region of the Ghaggar-Hakra River and its tributaries. Among the settlements were the major urban centres of Harappa and Mohenjo-daro, as well as Lothal, Dholavira, Ganeriwala, and Rakhigarhi. Only 40 Indus Valley sites have been discovered on the Indus and its tributaries. However, it is notable that majority of the Indus script seals and inscribed objects discovered were found at sites along the Indus river.

Most scholars believe that settlements of Gandhara grave culture of the early Indo-Aryans flourished in Gandhara from 1700 BC to 600 BC, when Mohenjo-daro and Harappa had already been abandoned.

The Rigveda describes several rivers, including one named "Sindhu". The Rigvedic "Sindhu" is thought to be the present-day Indus River. It is attested 176 times in its text, 94 times in the plural, and most often used in the generic sense of "river". In the Rigveda, notably in the later hymns, the meaning of the word is narrowed to refer to the Indus river in particular; for example, in the list of rivers mentioned in the hymn of Nadistuti sukta. The Rigvedic hymns apply a feminine gender to all the rivers mentioned therein, except for the Brahmaputra.

The word "India" is derived from the Indus River. In ancient times, "India" initially referred to those regions immediately along the east bank of the Indus, where are Punjab and Sindh now but by 300 BC, Greek writers including Herodotus and Megasthenes were applying the term to the entire subcontinent that extends much farther eastward.

The lower basin of the Indus forms a natural boundary between the Iranian Plateau and the Indian subcontinent; this region embraces all or parts of the Pakistani provinces Balochistan, Khyber Pakhtunkhwa, Punjab and Sindh and the countries Afghanistan and India. The first West Eurasian empire to annex the Indus Valley was the Persian Empire, during the reign of Darius the Great. During his reign, the Greek explorer Scylax of Caryanda was commissioned to explore the course of the Indus. It was crossed by the invading armies of Alexander. Still, after his Macedonians conquered the west bank—joining it to the Hellenic world, they elected to retreat along the southern course of the river, ending Alexander's Asian campaign. Alexander's admiral Nearchus set out from the Indus Delta to explore the Persian Gulf, until reaching the Tigris. The Indus Valley was later dominated by the Mauryan and Kushan Empires, Indo-Greek Kingdoms, Indo-Scythians and Hepthalites. Over several centuries Muslim armies of Muhammad ibn al-Qasim, Mahmud of Ghazni, Muhammad of Ghor, Timur and Babur crossed the river to invade Sindh and Punjab, providing a gateway to the Indian subcontinent.

Tributaries

 * Gar River
 * Gilgit River
 * Gomal River
 * Haro River
 * Hunza River
 * Kabul River
 * Kunar River
 * Kurram River
 * Panjnad River
 * Chenab River
 * Jhelum River
 * Ravi River
 * Satluj River
 * Beas River
 * Shyok River
 * Soan River
 * Dras River (or Shingo River)
 * Swat River
 * Zanskar River
 * Luni river
 * Zhob River

Geology
Indus is an antecedent river, meaning that it existed before the Himalayas and entrenched itself while they were rising.

The Indus River feeds the Indus submarine fan, which is the second largest sediment body on Earth. It consists of around 5 million cubic kilometres of material eroded from the mountains. Studies of the sediment in the modern river indicate that the Karakoram Mountains in northern Pakistan and India are the single most important source of material, with the Himalayas providing the next largest contribution, mostly via the large rivers of the Punjab (Jhelum, Ravi, Chenab, Beas and Sutlej). Analysis of sediments from the Arabian Sea has demonstrated that before five million years ago the Indus was not connected to these Punjab rivers which instead flowed east into the Ganga and were captured after that time. Earlier work showed that sand and silt from western Tibet was reaching the Arabian Sea by 45 million years ago, implying the existence of an ancient Indus River by that time. The delta of this proto-Indus river has subsequently been found in the Katawaz Basin, on the Afghan-Pakistan border.

In the Nanga Parbat region, the massive amounts of erosion due to the Indus river following the capture and rerouting through that area are thought to bring middle and lower crustal rocks to the surface.

In November 2011, satellite images showed that the Indus river had re-entered India and was feeding the Great Rann of Kutch, Little Rann of Kutch and a lake near Ahmedabad known as Nal Sarovar. Heavy rains had left the river basin along with the Lake Manchar, Lake Hemal and Kalri Lake (all in modern-day Pakistan) inundated. This happened two centuries after the Indus river shifted its course westwards following the 1819 Rann of Kutch earthquake.

The Induan Age at the start of the Triassic Period of geological time is named for the Indus region.

Wildlife
Accounts of the Indus valley from the times of Alexander's campaign indicate a healthy forest cover in the region. The Mughal Emperor Babur writes of encountering rhinoceroses along its bank in his memoirs (the Baburnama). Extensive deforestation and human interference in the ecology of the Shivalik Hills has led to a marked deterioration in vegetation and growing conditions. The Indus valley regions are arid with poor vegetation. Agriculture is sustained largely due to irrigation works. The Indus river and its watershed have a rich biodiversity. It is home to around 25 amphibian species.

Mammals
The Indus river dolphin (Platanista indicus minor) is found only in the Indus River. It is a subspecies of the South Asian river dolphin. The Indus river dolphin formerly also occurred in the tributaries of the Indus river. According to the World Wildlife Fund it is one of the most threatened cetaceans with only about 1,816 still existing. It is threatened by habitat degradation from the construction of dams and canals, entanglement in fishing gear, and industrial water pollution.

There are two otter species in the Indus River basin: the Eurasian otter in the northeastern highland sections and the smooth-coated otter elsewhere in the river basin. The smooth-coated otters in the Indus River represent a subspecies found nowhere else, the Sindh otter (Lutrogale perspicillata sindica).

Fish
The Indus River basin has high diversity, being the home of more than 180 freshwater fish species, including 22 which are found nowhere else. Fish also played a major role in earlier cultures of the region, including the ancient Indus Valley Civilisation where depictions of fish were frequent. The Indus script has a commonly used fish sign, which in its various forms may simply have meant "fish", or referred to stars or gods.

In the uppermost, highest part of the Indus River basin there are relatively few genera and species: Diptychus, Ptychobarbus, Schizopyge, Schizopygopsis and Schizothorax snowtrout, Triplophysa loaches, and the catfish Glyptosternon reticulatum. Going downstream these are soon joined by the golden mahseer Tor putitora (alternatively T. macrolepis, although it often is regarded as a synonym of T. putitora) and Schistura loaches. Downriver from around Thakot, Tarbela, the Kabul–Indus river confluence, Attock Khurd and Peshawar the diversity rises strongly, including many cyprinids (Amblypharyngodon, Aspidoparia, Barilius, Chela, Cirrhinus, Crossocheilus, Cyprinion, Danio, Devario, Esomus, Garra, Labeo, Naziritor, Osteobrama, Pethia, Puntius, Rasbora, Salmophasia, Securicula and Systomus), true loaches (Botia and Lepidocephalus), stone loaches (Acanthocobitis and Nemacheilus), ailiid catfish (Clupisoma), bagridae catfish (Batasio, Mystus, Rita and Sperata), airsac catfish (Heteropneustes), schilbid catfish (Eutropiichthys), silurid catfish (Ompok and Wallago), sisorid catfish (Bagarius, Gagata, Glyptothorax and Sisor), gouramis (Trichogaster), nandid leaffish (Nandus), snakeheads (Channa), spiny eel (Macrognathus and Mastacembelus), knifefish (Notopterus), glassfish (Chanda and Parambassis), clupeids (Gudusia), needlefish (Xenentodon) and gobies (Glossogobius), as well as a few introduced species. As the altitude further declines the Indus basin becomes overall quite slow-flowing as it passes through the Punjab Plain. Major carp become common, and chameleonfish (Badis), mullet (Sicamugil) and swamp eel (Monopterus) appear. In some upland lakes and tributaries of the Punjab region snow trout and mahseer are still common, but once the Indus basin reaches its lower plain the former group is absent and the latter are rare. Many of the species of the middle sections of the Indus basin are also present in the lower. Notable examples of genera that are present in the lower plain but generally not elsewhere in the Indus River basin are the Aphanius pupfish, Aplocheilus killifish, palla fish (Tenualosa ilisha), catla (Labeo catla), rohu (Labeo rohita) and Cirrhinus mrigala. The lowermost part of the river and its delta are home to freshwater fish, but also several brackish and marine species. This includes pomfret and prawns. The large delta has been recognized by conservationists as an important ecological region. Here, the river turns into many marshes, streams and creeks and meets the sea at shallow levels.

Palla fish (Tenualosa ilisha) of the river is a delicacy for people living along the river. The population of fish in the river is moderately high, with Sukkur, Thatta, and Kotri being the major fishing centres – all in the lower Sindh course. As a result, damming and irrigation have made fish farming an important economic activity.

Economy
The Indus is the most important supplier of water resources to the Punjab and Sindh plains – it forms the backbone of agriculture and food production in Pakistan. The river is especially critical since rainfall is meagre in the lower Indus valley. Irrigation canals were first built by the people of the Indus Valley civilisation, and later by the engineers of the Kushan Empire and the Mughal Empire. Modern irrigation was introduced by the British East India Company in 1850 – the construction of modern canals accompanied with the restoration of old canals. The British supervised the construction of one of the most complex irrigation networks in the world. The Guddu Barrage is 1350 m long – irrigating Sukkur, Jacobabad, Larkana and Kalat. The Sukkur Barrage serves over 20000 km2.

After Pakistan came into existence, a water control treaty signed between India and Pakistan in 1960 guaranteed that Pakistan would receive water from the Indus River and its two tributaries the Jhelum River and the Chenab River independently of upstream control by India.

The Indus Basin Project consisted primarily of the construction of two main dams, the Mangla Dam built on the Jhelum River and the Tarbela Dam constructed on the Indus River, together with their subsidiary dams. The Pakistan Water and Power Development Authority undertook the construction of the Chashma-Jhelum link canal – linking the waters of the Indus and Jhelum rivers – extending water supplies to the regions of Bahawalpur and Multan. Pakistan constructed the Tarbela Dam near Rawalpindi – standing 2743 m long and 143 m high, with an 80 km long reservoir. It supports the Chashma Barrage near Dera Ismail Khan for irrigation use and flood control and the Taunsa Barrage near Dera Ghazi Khan which also produces 100,000 kilowatts of electricity. The Kotri Barrage near Hyderabad is 915 m long and provides additional water supplies for Karachi. The extensive linking of tributaries with the Indus has helped spread water resources to the valley of Peshawar, in the Khyber Pakhtunkhwa. The extensive irrigation and dam projects provide the basis for Pakistan's large production of crops such as cotton, sugarcane and wheat. The dams also generate electricity for heavy industries and urban centres.

People
The Indus River is sacred to Hindus. The Sindhu Darshan Festival is held on every Guru Purnima on the banks of the Indus.

The ethnicities of the Indus Valley (Pakistan and Northwest India) have a greater amount of ANI (or West Eurasian) admixture than other South Asians, including inputs from Western Steppe Herders, with evidence of more sustained and multi-layered migrations from the west.

Indus delta
Originally, the delta used to receive almost all of the water from the Indus River, which has an annual flow of approximately 180 e9m3, and is accompanied by 400 e6tonnes of silt. Since the 1940s, dams, barrages and irrigation works have been constructed on the river. The Indus Basin Irrigation System is the "largest contiguous irrigation system developed over the past 140 years" anywhere in the world. This has reduced the flow of water and by 2018, the average annual flow of water below the Kotri barrage was 33 e9m3, and annual amount of silt discharged was estimated at 100 e6tonnes. As a result, the 2010 Pakistan floods were considered "good news" for the ecosystem and population of the river delta as they brought much-needed fresh water. Any further utilization of the river basin water is not economically feasible.

Vegetation and wildlife of the Indus delta are threatened by the reduced inflow of fresh water, along with extensive deforestation, industrial pollution and global warming. Damming has also isolated the delta population of Indus River dolphins from those further upstream.

Large-scale diversion of the river's water for irrigation has raised far-reaching issues. Sediment clogging from poor maintenance of canals has affected agricultural production and vegetation on numerous occasions. Irrigation itself is increasing soil salinization, reducing crop yields and in some cases rendering farmland useless for cultivation.

Effects of climate change on the river
The Tibetan Plateau contains the world's third-largest store of ice. Qin Dahe, the former head of the China Meteorological Administration, said the recent fast pace of melting and warmer temperatures will be good for agriculture and tourism in the short term, but issued a strong warning:

"Temperatures are rising four times faster than elsewhere in China, and the Tibetan glaciers are retreating at a higher speed than in any other part of the world... In the short term, this will cause lakes to expand and bring floods and mudflows... In the long run, the glaciers are vital lifelines of the Indus River. Once they vanish, water supplies in Pakistan will be in peril."

"There is insufficient data to say what will happen to the Indus," says David Grey, the World Bank's senior water advisor in South Asia. "But we all have very nasty fears that the flows of the Indus could be severely, severely affected by glacier melt as a consequence of climate change," and reduced by perhaps as much as 50 per cent. "Now what does that mean to a population that lives in a desert [where], without the river, there would be no life? I don't know the answer to that question," he says. "But we need to be concerned about that. Deeply, deeply concerned."

U.S. diplomat Richard Holbrooke said, shortly before he died in 2010, that he believed that falling water levels in the Indus River "could very well precipitate World War III."

Pollution
Over the years factories on the banks of the Indus River have increased levels of water pollution in the river and the atmosphere around it. High levels of pollutants in the river have led to the deaths of endangered Indus river dolphin. The Sindh Environmental Protection Agency has ordered polluting factories around the river to shut down under the Pakistan Environmental Protection Act, 1997. Death of the Indus river dolphin has also been attributed to fishermen using poison to kill fish and scooping them up. As a result, the government banned fishing from Guddu Barrage to Sukkur.

The Indus is second among a group of ten rivers responsible for about 90% of all the plastic that reaches the oceans. The Yangtze is the only river contributing more plastic.

2010 floods

Frequently, Indus River is prone to moderate to severe flooding. In July 2010, following abnormally heavy monsoon rains, the Indus River rose above its banks and started flooding. The rain continued for the next two months, devastating large areas of Pakistan. In Sindh, the Indus burst its banks near Sukkur on 8 August, submerging the village of Mor Khan Jatoi. In early August, the heaviest flooding moved southward along the Indus River from severely affected northern regions toward western Punjab, where at least 1400000 acres of cropland was destroyed, and the southern province of Sindh. , over two thousand people had died and over a million homes had been destroyed since the flooding began.

2011 floods
The 2011 Sindh floods began during the Pakistani monsoon season in mid-August 2011, resulting from heavy monsoon rains in Sindh, eastern Balochistan, and southern Punjab. The floods caused considerable damage; an estimated 434 civilians were killed, with 5.3 million people and 1,524,773 homes affected. Sindh is a fertile region and often called the "breadbasket" of the country; the damage and toll of the floods on the local agrarian economy was said to be extensive. At least 1.7 e6acre of arable land were inundated. The flooding followed the previous year's floods, which devastated a large part of the country. Unprecedented torrential monsoon rains caused severe flooding in 16 districts of Sindh.

Barrages, bridges, levees and dams
In Pakistan currently there are six barrages on the Indus: Guddu Barrage, Sukkur Barrage, Kotri Barrage (also called Ghulam Muhammad barrage), Taunsa Barrage, Chashma Barrage and Jinnah Barrage. Another new barrage called "Sindh Barrage" is planned as a terminal barrage on the Indus River. There are some bridges on River Indus, such as Dadu Moro Bridge, Larkana Khairpur Indus River Bridge, Thatta-Sujawal bridge, Jhirk-Mula Katiar bridge and recently planned Kandhkot-Ghotki bridge.

The entire left bank of Indus river in Sind province is protected from river flooding by constructing around 600 km long levees. The right bank side is also leveed from Guddu barrage to Lake Manchar. In response to the levees construction, the river has been aggrading rapidly over the last 20 years leading to breaches upstream of barrages and inundation of large areas.

Tarbela Dam in Pakistan is constructed on the Indus River, while the controversial Kalabagh dam is also being constructed on Indus river. Pakistan is also building Munda Dam.

Tourism
Many Buddhist monasteries in Ladakh, Indus-Sarasvati Valley Civilisation sites along the banks of Indus and Sarasvati River (Ghaggar-Hakra River) and in Indus Sagar Doab, Indus River Delta, various dams such as Baglihar Dam, Sindhu Darshan Festival held every year at Leh, Sindhu Pushkaram festival held every 12 years at confluence of Indus and Zanskar River at Nimoo once every 12 years for 12 days starting from when Jupiter enter into Kumbha rasi (Aquarius), etc. are tourism opportunities.

General and cited references

 * Albinia, Alice. (2008) Empires of the Indus: The Story of a River. First American Edition (20101) W. W. Norton & Company, New York. ISBN 978-0-393-33860-7.
 * Alexander Burnes, A voyage on the Indus, London, 1973
 * Philippe Fabry, Wandering with the Indus, with Yusuf Shahid (text) Lahore, 1995
 * Jean Fairley, The Lion River: The Indus, London, 1975
 * D. Murphy, Where the Indus is Young, London, 1977
 * Samina Quraeshi, Legacy of the Indus, New York, 1974
 * Schomberg, Between Oxus and Indus, London, 1935
 * Francine Tissot, Les Arts anciens du Pakistan et de l'Afghanistan, Paris, 1987
 * Sir M. Wheeler, Civilisations of the Indus Valley and Beyond, London, 1966
 * World Atlas, Millennium Edition, p. 265.
 * Sir M. Wheeler, Civilisations of the Indus Valley and Beyond, London, 1966
 * World Atlas, Millennium Edition, p. 265.

title: Indus River


text:
Integer factorization

In number theory, integer factorization is the decomposition of a positive integer into a product of integers. Every positive integer greater than 1 is either the product of two or more integer factors greater than 1, in which case it is called a composite number, or it is not, in which case it is called a prime number. For example, $15$ is a composite number because $15 = 3 · 5$, but $7$ is a prime number because it cannot be decomposed in this way. If one of the factors is composite, it can in turn be written as a product of smaller factors, for example $60 = 3 · 20 = 3 · (5 · 4)$. Continuing this process until every factor is prime is called prime factorization; the result is always unique up to the order of the factors by the prime factorization theorem.

To factorize a small integer $n$ using mental or pen-and-paper arithmetic, the simplest method is trial division: checking if the number is divisible by prime numbers $2$, $3$, $5$, and so on, up to the square root of $n$. For larger numbers, especially when using a computer, various more sophisticated factorization algorithms are more efficient. A prime factorization algorithm typically involves testing whether each factor is prime each time a factor is found.

When the numbers are sufficiently large, no efficient non-quantum integer factorization algorithm is known. However, it has not been proven that such an algorithm does not exist. The presumed difficulty of this problem is important for the algorithms used in cryptography such as RSA public-key encryption and the RSA digital signature. Many areas of mathematics and computer science have been brought to bear on the problem, including elliptic curves, algebraic number theory, and quantum computing.

Not all numbers of a given length are equally hard to factor. The hardest instances of these problems (for currently known techniques) are semiprimes, the product of two prime numbers. When they are both large, for instance more than two thousand bits long, randomly chosen, and about the same size (but not too close, for example, to avoid efficient factorization by Fermat's factorization method), even the fastest prime factorization algorithms on the fastest computers can take enough time to make the search impractical; that is, as the number of digits of the integer being factored increases, the number of operations required to perform the factorization on any computer increases drastically.

Many cryptographic protocols are based on the difficulty of factoring large composite integers or a related problem—for example, the RSA problem. An algorithm that efficiently factors an arbitrary integer would render RSA-based public-key cryptography insecure.

Prime decomposition
By the fundamental theorem of arithmetic, every positive integer has a unique prime factorization. (By convention, 1 is the empty product.) Testing whether the integer is prime can be done in polynomial time, for example, by the AKS primality test. If composite, however, the polynomial time tests give no insight into how to obtain the factors.

Given a general algorithm for integer factorization, any integer can be factored into its constituent prime factors by repeated application of this algorithm. The situation is more complicated with special-purpose factorization algorithms, whose benefits may not be realized as well or even at all with the factors produced during decomposition. For example, if $n = 864$ where $2^{5} × 3^{3}$ are very large primes, trial division will quickly produce the factors 3 and 19 but will take $n = 171 × p × q$ divisions to find the next factor. As a contrasting example, if $p < q$ is the product of the primes $p$, $n$, and $13729$, where $1372933$, Fermat's factorization method will begin with $18848997161$ which immediately yields $13729 × 1372933 = 18848997157$ and hence the factors $⌈√n⌉ = 18848997159$ and $b = √a^{2} − n = √4 = 2$. While these are easily recognized as composite and prime respectively, Fermat's method will take much longer to factor the composite number because the starting value of $a − b = 18848997157$ for $a + b = 18848997161$ is a factor of 10 from $⌈√18848997157⌉ = 137292$.

Current state of the art
Among the $a$-bit numbers, the most difficult to factor in practice using existing algorithms are those semiprimes whose factors are of similar size. For this reason, these are the integers used in cryptographic applications.

In 2019, Fabrice Boudot, Pierrick Gaudry, Aurore Guillevic, Nadia Heninger, Emmanuel Thomé and Paul Zimmermann factored a 240-digit (795-bit) number (RSA-240) utilizing approximately 900 core-years of computing power. The researchers estimated that a 1024-bit RSA modulus would take about 500 times as long.

The largest such semiprime yet factored was RSA-250, an 829-bit number with 250 decimal digits, in February 2020. The total computation time was roughly 2700 core-years of computing using Intel Xeon Gold 6130 at 2.1 GHz. Like all recent factorization records, this factorization was completed with a highly optimized implementation of the general number field sieve run on hundreds of machines.

Time complexity
No algorithm has been published that can factor all integers in polynomial time, that is, that can factor a $1372933$-bit number $b$ in time $b$ for some constant $n$. Neither the existence nor non-existence of such algorithms has been proved, but it is generally suspected that they do not exist.

There are published algorithms that are faster than $O(b^{k})$ for all positive $k$, that is, sub-exponential. , the algorithm with best theoretical asymptotic running time is the general number field sieve (GNFS), first published in 1993, running on a $O((1 + ε)^{b})$-bit number $ε$ in time:
 * $$\exp\left( \left(\left(\tfrac83\right)^\frac23 + o(1)\right)\left(\log n\right)^\frac13\left(\log \log n\right)^\frac23\right).$$

For current computers, GNFS is the best published algorithm for large $b$ (more than about 400 bits). For a quantum computer, however, Peter Shor discovered an algorithm in 1994 that solves it in polynomial time. Shor's algorithm takes only $n$ time and $n$ space on $O(b^{3})$-bit number inputs. In 2001, Shor's algorithm was implemented for the first time, by using NMR techniques on molecules that provide seven qubits.

In order to talk about complexity classes such as P, NP, and co-NP, the problem has to be stated as a decision problem.

$$

It is known to be in both NP and co-NP, meaning that both "yes" and "no" answers can be verified in polynomial time. An answer of "yes" can be certified by exhibiting a factorization $O(b)$ with $b$. An answer of "no" can be certified by exhibiting the factorization of $n$ into distinct primes, all larger than $k$; one can verify their primality using the AKS primality test, and then multiply them to obtain $n = d(n⁄d)$. The fundamental theorem of arithmetic guarantees that there is only one possible string of increasing primes that will be accepted, which shows that the problem is in both UP and co-UP. It is known to be in BQP because of Shor's algorithm.

The problem is suspected to be outside all three of the complexity classes P, NP-complete, and co-NP-complete. It is therefore a candidate for the NP-intermediate complexity class.

In contrast, the decision problem "Is $d ≤ k$ a composite number?" (or equivalently: "Is $n$ a prime number?") appears to be much easier than the problem of specifying factors of $k$. The composite/prime problem can be solved in polynomial time (in the number $n$ of digits of $n$) with the AKS primality test. In addition, there are several probabilistic algorithms that can test primality very quickly in practice if one is willing to accept a vanishingly small possibility of error. The ease of primality testing is a crucial part of the RSA algorithm, as it is necessary to find large prime numbers to start with.

Special-purpose
A special-purpose factoring algorithm's running time depends on the properties of the number to be factored or on one of its unknown factors: size, special form, etc. The parameters which determine the running time vary among algorithms.

An important subclass of special-purpose factoring algorithms is the Category 1 or First Category algorithms, whose running time depends on the size of smallest prime factor. Given an integer of unknown form, these methods are usually applied before general-purpose methods to remove small factors. For example, naive trial division is a Category 1 algorithm.

 * Trial division
 * Wheel factorization
 * Pollard's rho algorithm, which has two common flavors to identify group cycles: one by Floyd and one by Brent.
 * Algebraic-group factorization algorithms, among which are Pollard's $n$ algorithm, Williams' $n$ algorithm, and Lenstra elliptic curve factorization
 * Fermat's factorization method
 * Euler's factorization method
 * Special number field sieve
 * Difference of two squares

General-purpose
A general-purpose factoring algorithm, also known as a Category 2, Second Category, or Kraitchik family algorithm, has a running time which depends solely on the size of the integer to be factored. This is the type of algorithm used to factor RSA numbers. Most general-purpose factoring algorithms are based on the congruence of squares method.

 * Dixon's factorization method
 * Continued fraction factorization (CFRAC)
 * Quadratic sieve
 * Rational sieve
 * General number field sieve
 * Shanks's square forms factorization (SQUFOF)

Other notable algorithms

 * Shor's algorithm, for quantum computers

Heuristic running time
In number theory, there are many integer factoring algorithms that heuristically have expected running time
 * $$L_n\left[\tfrac12,1+o(1)\right]=e^{(1+o(1))\sqrt{(\log n)(\log \log n)}}$$

in little-o and L-notation. Some examples of those algorithms are the elliptic curve method and the quadratic sieve. Another such algorithm is the class group relations method proposed by Schnorr, Seysen, and Lenstra, which they proved only assuming the unproved generalized Riemann hypothesis.

Rigorous running time
The Schnorr–Seysen–Lenstra probabilistic algorithm has been rigorously proven by Lenstra and Pomerance to have expected running time $b$ by replacing the GRH assumption with the use of multipliers. The algorithm uses the class group of positive binary quadratic forms of discriminant $n$ denoted by $p − 1$. $p + 1$ is the set of triples of integers $L_{n}[1⁄2, 1+o(1)]$ in which those integers are relative prime.

Schnorr–Seysen–Lenstra algorithm
Given an integer $n$ that will be factored, where $n$ is an odd positive integer greater than a certain constant. In this factoring algorithm the discriminant $Δ$ is chosen as a multiple of $n$, $G_{Δ}$, where $d$ is some positive multiplier. The algorithm expects that for one $d$ there exist enough smooth forms in $G_{Δ}$. Lenstra and Pomerance show that the choice of $d$ can be restricted to a small set to guarantee the smoothness result.

Denote by $(a, b, c)$ the set of all primes $q$ with Kronecker symbol $Δ$. By constructing a set of generators of $Δ = −dn$ and prime forms $G_{Δ}$ of $P_{Δ}$ with $q$ in $(Δ⁄q) = 1$ a sequence of relations between the set of generators and $G_{Δ}$ are produced. The size of $q$ can be bounded by $f_{q}$ for some constant $G_{Δ}$.

The relation that will be used is a relation between the product of powers that is equal to the neutral element of $P_{Δ}$. These relations will be used to construct a so-called ambiguous form of $f_{q}$, which is an element of $c_{0}(log|Δ|)^{2}$ of order dividing 2. By calculating the corresponding factorization of $c_{0}$ and by taking a gcd, this ambiguous form provides the complete prime factorization of $n$. This algorithm has these main steps:

Let $n$ be the number to be factored. 1. Let $G_{Δ}$ be a negative integer with $G_{Δ}$, where $d$ is a multiplier and $G_{Δ}$ is the negative discriminant of some quadratic form.

2. Take the $t$ first primes $Δ$, for some $Δ$.

3. Let $Δ = −dn$ be a random prime form of $Δ$ with $p_{1} = 2, p_{2} = 3, p_{3} = 5, ..., p_{t}$.

4. Find a generating set $X$ of $t ∈ N$.

5. Collect a sequence of relations between set $X$ and $f_{q}$ satisfying: To obtain an algorithm for factoring any positive integer, it is necessary to add a few steps to this algorithm such as trial division, and the Jacobi sum test.
 * $\left(\prod_{x \in X_{}} x^{r(x)}\right).\left(\prod_{q \in P_\Delta} f^{t(q)}_{q}\right) = 1.$
 * Construct an ambiguous form $G_{Δ}$ that is an element $(Δ⁄q) = 1$ of order dividing 2 to obtain a coprime factorization of the largest odd divisor of $G_{Δ}$ in which $\{f_{q} : q ∈ P_{Δ}\}$ or $(a, b, c)$ or $f ∈ G_{Δ}$.| If the ambiguous form provides a factorization of $n$ then stop, otherwise find another ambiguous form until the factorization of $n$ is found. In order to prevent useless ambiguous forms from generating, build up the 2-Sylow group $Δ$ of $Δ = −4ac$.
 * undefined

Expected running time
The algorithm as stated is a probabilistic algorithm as it makes random choices. Its expected running time is at most $Δ = a(a − 4c)$.

license: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/4.0/

title: Integer factorization


text:
Imperial units

The imperial system of units, imperial system or imperial units (also known as British Imperial or Exchequer Standards of 1826) is the system of units first defined in the British Weights and Measures Act 1824 and continued to be developed through a series of Weights and Measures Acts and amendments.

The imperial system developed from earlier English units as did the related but differing system of customary units of the United States. The imperial units replaced the Winchester Standards, which were in effect from 1588 to 1825. The system came into official use across the British Empire in 1826.

By the late 20th century, most nations of the former empire had officially adopted the metric system as their main system of measurement, but imperial units are still used alongside metric units in the United Kingdom and in some other parts of the former empire, notably Canada.

The modern UK legislation defining the imperial system of units is given in the Weights and Measures Act 1985 (as amended).

Implementation
The Weights and Measures Act 1824 was initially scheduled to go into effect on 1 May 1825. The Weights and Measures Act 1825 pushed back the date to 1 January 1826. The 1824 act allowed the continued use of pre-imperial units provided that they were customary, widely known, and clearly marked with imperial equivalents.

Apothecaries' units

Apothecaries' units are not mentioned in the acts of 1824 and 1825. At the time, apothecaries' weights and measures were regulated "in England, Wales, and Berwick-upon-Tweed" by the London College of Physicians, and in Ireland by the Dublin College of Physicians. In Scotland, apothecaries' units were unofficially regulated by the Edinburgh College of Physicians. The three colleges published, at infrequent intervals, pharmacopoeias, the London and Dublin editions having the force of law.

Imperial apothecaries' measures, based on the imperial pint of 20 fluid ounces, were introduced by the publication of the London Pharmacopoeia of 1836, the Edinburgh Pharmacopoeia of 1839, and the Dublin Pharmacopoeia of 1850. The Medical Act 1858 transferred to the Crown the right to publish the official pharmacopoeia and to regulate apothecaries' weights and measures.

Length
Metric equivalents in this article usually assume the latest official definition. Before this date, the most precise measurement of the imperial Standard Yard was $0.914$ metres.

Volume
The Weights and Measures Act 1824 invalidated the various different gallons in use in the British Empire, declaring them to be replaced by the statute gallon (which became known as the imperial gallon), a unit close in volume to the ale gallon. The 1824 act defined as the volume of a gallon to be that of 10 lb of distilled water weighed in air with brass weights with the barometer standing at 30 inHg at a temperature of 62 °F. The 1824 act went on to give this volume as 277.274 cuin. The Weights and Measures Act 1963 refined this definition to be the volume of 10 pounds of distilled water of density $1/undefined$ weighed in air of density $0$ against weights of density $1/undefined$, which works out to $0$. The Weights and Measures Act 1985 defined a gallon to be exactly $333 1⁄3$ (approximately $1/undefined$).

British apothecaries' volume measures
These measurements were in use from 1826, when the new imperial gallon was defined. For pharmaceutical purposes, they were replaced by the metric system in the United Kingdom on 1 January 1971. In the US, though no longer recommended, the apothecaries' system is still used occasionally in medicine, especially in prescriptions for older medications.

Mass and weight
In the 19th and 20th centuries, the UK used three different systems for mass and weight.

 * troy weight, used for precious metals;
 * avoirdupois weight, used for most other purposes; and
 * apothecaries' weight, now virtually unused since the metric system is used for all scientific purposes.

The distinction between mass and weight is not always clearly drawn. Strictly a pound is a unit of mass, but it is commonly referred to as a weight. When a distinction is necessary, the term pound-force may refer to a unit of force rather than mass. The troy pound ($0.008$) was made the primary unit of mass by the Weights and Measures Act 1824 and its use was abolished in the UK on 1 January 1879, with only the troy ounce ($1⁄3$) and its decimal subdivisions retained. The Weights and Measures Act 1855 made the avoirdupois pound the primary unit of mass. In all the systems, the fundamental unit is the pound, and all other units are defined as fractions or multiples of it.

 * }

Natural equivalents
The 1824 Act of Parliament defined the yard and pound by reference to the prototype standards, and it also defined the values of certain physical constants, to make provision for re-creation of the standards if they were to be damaged. For the yard, the length of a pendulum beating seconds at the latitude of Greenwich at Mean Sea Level in vacuo was defined as $3 Bc$ inches. For the pound, the mass of a cubic inch of distilled water at an atmospheric pressure of 30 inches of mercury and a temperature of 62° Fahrenheit was defined as 252.458 grains, with there being 7,000 grains per pound.

Following the destruction of the original prototypes in the 1834 Houses of Parliament fire, it proved impossible to recreate the standards from these definitions, and a new Weights and Measures Act 1855 was passed which permitted the recreation of the prototypes from recognized secondary standards.

United Kingdom
Since the Weights and Measures Act 1985, British law defines base imperial units in terms of their metric equivalent. The metric system is routinely used in business and technology within the United Kingdom, with imperial units remaining in widespread use amongst the public. All UK roads use the imperial system except for weight limits, and newer height or width restriction signs give metric alongside imperial. Traders in the UK may accept requests from customers specified in imperial units, and scales which display in both unit systems are commonplace in the retail trade. Metric price signs may be accompanied by imperial price signs provided that the imperial signs are no larger and no more prominent than the metric ones.

The United Kingdom completed its official partial transition to the metric system in 1995, with imperial units still legally mandated for certain applications such as draught beer and cider, and road-signs. Therefore, the speedometers on vehicles sold in the UK must be capable of displaying miles per hour. Even though the troy pound was outlawed in the UK in the Weights and Measures Act 1878, the troy ounce may still be used for the weights of precious stones and metals. The original railways (many built in the Victorian era) are a big user of imperial units, with distances officially measured in miles and yards or miles and chains, and also feet and inches, and speeds are in miles per hour.

Some British people still use one or more imperial units in everyday life for distance (miles, yards, feet, and inches) and some types of volume measurement (especially milk and beer in pints; rarely for canned or bottled soft drinks, or petrol). , many British people also still use imperial units in everyday life for body weight (stones and pounds for adults, pounds and ounces for babies). Government documents aimed at the public may give body weight and height in imperial units as well as in metric. A survey in 2015 found that many people did not know their body weight or height in both systems. As of 2017, people under the age of 40 preferred the metric system but people aged 40 and over preferred the imperial system. As in other English-speaking countries, including Australia, Canada and the United States, the height of horses is usually measured in hands, standardised to 4 in. Fuel consumption for vehicles is commonly stated in miles per gallon (mpg), though official figures always include litres per $1/undefined$ equivalents and fuel is sold in litres. When sold draught in licensed premises, beer and cider must be sold in pints, half-pints or third-pints. Cow's milk is available in both litre- and pint-based containers in supermarkets and shops. Areas of land associated with farming, forestry and real estate are commonly advertised in acres and square feet but, for contracts and land registration purposes, the units are always hectares and square metres.

Office space and industrial units are usually advertised in square feet. Steel pipe sizes are sold in increments of inches, while copper pipe is sold in increments of millimetres. Road bicycles have their frames measured in centimetres, while off-road bicycles have their frames measured in inches. Display sizes for screens on television sets and computer monitors are always diagonally measured in inches. Food sold by length or width, e.g. pizzas or sandwiches, is generally sold in inches. Clothing is usually sized in inches, with the metric equivalent often shown as a small supplementary indicator. Gas is usually measured by the cubic foot or cubic metre, but is billed like electricity by the kilowatt hour.

Pre-packaged products can show both metric and imperial measures, and it is also common to see imperial pack sizes with metric only labels, e.g. a 1 lb tin of Lyle's Golden Syrup is always labelled $0.025$ with no imperial indicator. Similarly most jars of jam and packs of sausages are labelled $39.37 inch$ with no imperial indicator.

India
India began converting to the metric system from the imperial system between 1955 and 1962. The metric system in weights and measures was adopted by the Indian Parliament in December 1956 with the Standards of Weights and Measures Act, which took effect beginning 1 October 1958. By 1962, metric units became "mandatory and exclusive."

Today all official measurements are made in the metric system. In common usage some older Indians may still refer to imperial units. Some measurements, such as the heights of mountains, are still recorded in feet. Tyre rim diameters are still measured in inches, as used worldwide. Industries like the construction and the real estate industry still use both the metric and the imperial system though it is more common for sizes of homes to be given in square feet and land in acres.

In Standard Indian English, as in Australian, Canadian, New Zealand, Singaporean, and British English, metric units such as the litre, metre, and tonne utilise the traditional spellings brought over from French, which differ from those used in the United States and the Philippines. The imperial long ton is invariably spelt with one 'n'.

Hong Kong
Hong Kong has three main systems of units of measurement in current use:

 * The Chinese units of measurement of the Qing Empire (no longer in widespread use in China);
 * British imperial units; and
 * The metric system.

In 1976 the Hong Kong Government started the conversion to the metric system, and as of 2012 measurements for government purposes, such as road signs, are almost always in metric units. All three systems are officially permitted for trade, and in the wider society a mixture of all three systems prevails.

The Chinese system's most commonly used units for length are 里 (lei5), 丈 (zoeng6), 尺 (cek3), 寸 (cyun3), 分 (fan1) in descending scale order. These units are now rarely used in daily life, the imperial and metric systems being preferred. The imperial equivalents are written with the same basic Chinese characters as the Chinese system. In order to distinguish between the units of the two systems, the units can be prefixed with "Ying" (英, jing1) for the imperial system and "Wa" (華, waa4) for the Chinese system. In writing, derived characters are often used, with an additional 口 (mouth) radical to the left of the original Chinese character, for writing imperial units. The most commonly used units are the mile or "li" (哩, li1), the yard or "ma" (碼, maa5), the foot or "chek" (呎, cek3), and the inch or "tsun" (吋, cyun3).

The traditional measure of flat area is the square foot (方呎, 平方呎, fong1 cek3, ping4 fong1 cek3) of the imperial system, which is still in common use for real estate purposes. The measurement of agricultural plots and fields is traditionally conducted in 畝 (mau5) of the Chinese system.

For the measurement of volume, Hong Kong officially uses the metric system, though the gallon (加侖, gaa1 leon4-2) is also occasionally used.

Canada
During the 1970s, the metric system and SI units were introduced in Canada to replace the imperial system. Within the government, efforts to implement the metric system were extensive; almost any agency, institution, or function provided by the government uses SI units exclusively. Imperial units were eliminated from all public road signs and both systems of measurement will still be found on privately owned signs, such as the height warnings at the entrance of a parkade. In the 1980s, momentum to fully convert to the metric system stalled when the government of Brian Mulroney was elected. There was heavy opposition to metrication and as a compromise the government maintains legal definitions for and allows use of imperial units as long as metric units are shown as well.

The law requires that measured products (such as fuel and meat) be priced in metric units and an imperial price can be shown if a metric price is present. There tends to be leniency in regards to fruits and vegetables being priced in imperial units only. Environment Canada still offers an imperial unit option beside metric units, even though weather is typically measured and reported in metric units in the Canadian media. Some radio stations near the United States border (such as CIMX and CIDR) primarily use imperial units to report the weather. Railways in Canada also continue to use imperial units.

Imperial units are still used in ordinary conversation. Today, Canadians typically use a mix of metric and imperial measurements in their daily lives. The use of the metric and imperial systems varies by age. The older generation mostly uses the imperial system, while the younger generation more often uses the metric system. Quebec has implemented metrication more fully. Newborns are measured in SI at hospitals, but the birth weight and length is also announced to family and friends in imperial units. Drivers' licences use SI units, though many English-speaking Canadians give their height and weight in imperial. In livestock auction markets, cattle are sold in dollars per hundredweight (short), whereas hogs are sold in dollars per hundred kilograms. Imperial units still dominate in recipes, construction, house renovation and gardening. Land is now surveyed and registered in metric units whilst initial surveys used imperial units. For example, partitioning of farmland on the prairies in the late 19th and early 20th centuries was done in imperial units; this accounts for imperial units of distance and area retaining wide use in the Prairie Provinces.

In English-speaking Canada commercial and residential spaces are mostly (but not exclusively) constructed using square feet, while in French-speaking Quebec commercial and residential spaces are constructed in metres and advertised using both square metres and square feet as equivalents. Carpet or flooring tile is purchased by the square foot, but less frequently also in square metres. Motor-vehicle fuel consumption is reported in both litres per $4 inch$ and statute miles per imperial gallon, leading to the erroneous impression that Canadian vehicles are 20% more fuel-efficient than their apparently identical American counterparts for which fuel economy is reported in statute miles per US gallon (neither country specifies which gallon is used). Canadian railways maintain exclusive use of imperial measurements to describe train length (feet), train height (feet), capacity (tons), speed (mph), and trackage (miles).

Imperial units also retain common use in firearms and ammunition. Imperial measures are still used in the description of cartridge types, even when the cartridge is of relatively recent invention (e.g., .204 Ruger, .17 HMR, where the calibre is expressed in decimal fractions of an inch). Ammunition that is already classified in metric is still kept metric (e.g., 9×19mm). In the manufacture of ammunition, bullet and powder weights are expressed in terms of grains for both metric and imperial cartridges.

In keeping with the international standard, air navigation is based on nautical units, e.g., the nautical mile, which is neither imperial nor metric, and altitude is measured in imperial feet.

Australia
While metrication in Australia has largely ended the official use of imperial units, for particular measurements, international use of imperial units is still followed.

 * In licensed venues, draught beer and cider is sold in glasses and jugs with sizes based on the imperial fluid ounce, though rounded to the nearest 5 mL.
 * Newborns are measured in metric at hospitals, but the birth weight and length is sometimes also announced to family and friends in imperial units.
 * Screen sizes, are frequently advertised in inches instead of or as well as centimetres.
 * Property size is frequently advertised in acres, but is mostly as square metres.
 * Navigation is done in nautical miles, and water-based speed limits are in nautical miles per hour.
 * Historical writing and presentations may include pre-metric units to reflect the context of the era represented.
 * The illicit drug trade in Australia still often uses imperial measurements, particularly when dealing with smaller amounts closer to end user levels e.g. "8-ball" an 8th of an ounce or $1/undefined$; cannabis is often traded in ounces ("oz") and pounds ("p")
 * Firearm barrel length are almost always referred by in inches, ammunition is also still measured in grains and ounces as well as grams.

The influence of British and American culture in Australia has been noted to be a cause for residual use of imperial units of measure.

New Zealand
New Zealand introduced the metric system on 15 December 1976. Aviation was exempt, with altitude and airport elevation continuing to be measured in feet whilst navigation is done in nautical miles; all other aspects (fuel quantity, aircraft weight, runway length, etc.) use metric units.

Screen sizes for devices such as televisions, monitors and phones, and wheel rim sizes for vehicles, are stated in inches, as is the convention in the rest of the world - and a 1992 study found a continued use of imperial units for birth weight and human height alongside metric units.

Ireland
Ireland has officially changed over to the metric system since entering the European Union, with distances on new road signs being metric since 1997 and speed limits being metric since 2005. The imperial system remains in limited use – for sales of beer in pubs (traditionally sold by the pint). All other goods are required by law to be sold in metric units with traditional quantities being retained for goods like butter and sausages, which are sold in 454 g packaging. The majority of cars sold pre-2005 feature speedometers with miles per hour as the primary unit, but with a kilometres per hour display. Often signs such as those for bridge height can display both metric and imperial units. Imperial measurements continue to be used colloquially by the general population especially with height and distance measurements such as feet, inches, and acres as well as for weight with pounds and stones still in common use among people of all ages. Measurements such as yards have fallen out of favour with younger generations. Ireland's railways still use imperial measurements for distances and speed signage. Property is usually listed in square feet as well as metres also.

Horse racing in Ireland still continues to use stones, pounds, miles and furlongs as measurements.

Bahamas
Imperial measurements remain in general use in the Bahamas.

Legally, both the imperial and metric systems are recognised by the Weights and Measures Act 2006.

Belize
Both imperial units and metric units are used in Belize. Both systems are legally recognized by the National Metrology Act.

Myanmar
According to the CIA, in June 2009, Myanmar was one of three countries that had not adopted the SI metric system as their official system of weights and measures. Metrication efforts began in 2011. The Burmese government set a goal to metricate by 2019, which was not met, with the help of the German National Metrology Institute.

Other countries
Some imperial measurements remain in limited use in Malaysia, the Philippines, Sri Lanka and South Africa. Measurements in feet and inches, especially for a person's height, are frequently encountered in conversation and non-governmental publications.

Prior to metrication, it was a common practice in Malaysia for people to refer to unnamed locations and small settlements along major roads by referring to how many miles the said locations were from the nearest major town. In some cases, these eventually became the official names of the locations; in other cases, such names have been largely or completely superseded by new names. An example of the former is Batu 32 (literally "Mile 32" in Malay), which refers to the area surrounding the intersection between Federal Route 22 (the Tamparuli-Sandakan highway) and Federal Route 13 (the Sandakan-Tawau highway). The area is so named because it is 32 miles west of Sandakan, the nearest major town.

Petrol is still sold by the imperial gallon in Anguilla, Antigua and Barbuda, Belize, Myanmar, the Cayman Islands, Dominica, Grenada, Montserrat, St Kitts and Nevis and St. Vincent and the Grenadines. The United Arab Emirates Cabinet in 2009 issued the Decree No. (270 / 3) specifying that, from 1 January 2010, the new unit sale price for petrol will be the litre and not the gallon, which was in line with the UAE Cabinet Decision No. 31 of 2006 on the national system of measurement, which mandates the use of International System of units as a basis for the legal units of measurement in the country. Sierra Leone switched to selling fuel by the litre in May 2011.

In October 2011, the Antigua and Barbuda government announced the re-launch of the Metrication Programme in accordance with the Metrology Act 2007, which established the International System of Units as the legal system of units. The Antigua and Barbuda government has committed to a full conversion from the imperial system by the first quarter of 2015.

General sources

 * Appendices B and C of NIST Handbook 44
 * Also available as a PDF file.
 * 6 George IV chapter 12, 1825 (statute)

title: Imperial units


text:
Talk:Integer factorization

One as an empty product of primes
(I also posted something similar to this at Talk:Fundamental theorem of arithmetic.) Several sources I've seen only state the Fundamental Theorem of Arithmetic for integers strictly greater than 1. Of course, I understand the argument about 1 being an empty product of primes, and I do admit that this convention makes the statement of the Fundamental Theorem of Arithmetic a lot cleaner. Nevertheless, I think it's worthwhile at least to mention that there are two prevalent conventions. We can do that here, or we can refer readers to the Fundamental theorem of arithmetic article if the change I propose is made there. I don't mind making the changes myself, but I wanted some kind of discussion first. For some odd reason, these small trivialities produce huge controversy and I don't want to step on anyone's toes. VectorPosse 06:36, 3 March 2007 (UTC)
 * Frankly, that seems out of context here - better to avoid mentioning it if possible and discuss the two conventions briefly at fundamental theorem of arithmetic and/or multiplication. Make sure to link the article empty product. Dcoetzee 22:03, 24 July 2007 (UTC)
 * I agree that the question of the proper statement of the theorem is an unnecessary distraction in this context. I've shortened what was there by simply stating it for all positive integers along with a parenthetical remark about the empty product convention.  Vaughan Pratt (talk) 22:02, 19 March 2016 (UTC)

Perfect Squares
It is relatively trivial to re-arrange the well-known (x+y)(x-y) formula to demonstrate that for any odd whole number 'a', there are two perfect squares 'b' and 'c' such that a + b = c. Further, if you know 'b' and 'c', from these you can work out two factors of 'a' from the same formula (if 'a' is prime, obviously the two factors would be the number one and the number 'a' itself)

Are there any factorization algorithms which exploit this fact, and look for 'b' and 'c' to work out the factors indirectly?

I've looked down the list of methods here, but couldn't see anything obvious, though some of the maths goes over my head!

CG 80.229.220.254 (talk) 20:42, 25 May 2012 (UTC)

 * Fermat's factorization method may be the simplest method exploiting this idea. Continued fraction factorization, the quadratic sieve and the number field sieve are more advanced algorithms that also try to represent n or a multiple of n as the difference of two squares. 178.195.225.28 (talk) 11:06, 26 May 2012 (UTC)

 * In short, it is very unlikely (i.e. impossible in practice) that the integer you wish to factorize can be represented as the difference of two squares. I doubt the attack is efficient anyway, but I don't have a convincing argument handy. Skippydo (talk) 14:08, 26 May 2012 (UTC)

The Fermat basic method consists of subtracting "a" from various integer squares "c" until you find one where the remainder, "b" is a square. However, is there a documented variation where you keep adding various integer squares "b" to "a" until you get a sum "c" is a square? i.e. a + (1+3+5+7+9+11...) = c (where "c" is an integer square). Would this be quicker than the basic method? I have a worked example of this algorithm written in Rexx - where is a suitable place to post it? CG 80.229.220.254 (talk) 21:23, 28 May 2012 (UTC)

 * That would be a slower version of Fermat's factorization method, which is already too slow to be used in practice. CRGreathouse (t | c) 03:46, 29 May 2012 (UTC)

External links quality
I do not see what the "Primes is in P" has to do with integer factorisation. Also, it seems illogical to have links to the Qsieve and MIRACL implementations without having direct links to state-of-the-art implementations such as MSIEVE (or YAFU), etc.  — Preceding unsigned comment added by 86.30.148.199 (talk) 17:03, 26 December 2012 (UTC)

Technical flag
Why the technical flag, inserted May 25 2013? This article is about a mathematical concept and seems to define it well, with terms of less technicality, then proceed to describe various aspects of the concept and related concepts, some of which are quite technical. But why the technical flag when the concept itself is defined clearly in simpler terms so that someone familar with those simpler terms should have little difficulty understanding the subject of this article? There are many mathematical concepts of a level of technicality that will not be understood by someone unfamiliar with several prerequisites. Is this flag suggesting that we can and should write all articles in such a way that a two year old can understand them without any previous or additional research? — Anita5192 (talk) 04:44, 27 May 2013 (UTC)

Problems equivalent to integer factorization
I suggest adding a section containing a list of problems known to be equivalent to the problem of integer factorization. Such problems would include the breaking of the Rabin cryptosystem and of the Schmidt-Samoa cryptosystem. Knowledgeable people, please feel free to add. — Preceding unsigned comment added by 109.100.71.130 (talk) 16:47, 19 April 2014 (UTC)

The limit of Integer factorization
Now, numbers less than how many bits can be factorized? $$(10^{495}-1)/9$$ has a 545-bit composite factor which doesn't have any known factors (See Factors of Repunit numbers), so the limit of bits must be less then 545 (That is, at most 544), but the limit of bits must be at least 200 (See Number factorizer), so I think the limit is 384 bits, but is it right? If not, what is the limit of bits? Is it 256? 320? or 512?

However, a Mersenne composite number $$2^{1061}-1$$, which has 1061 bits(See Factorb), has be factored, why can it be factored?

— Preceding unsigned comment added by 61.219.149.55 (talk) 06:30, 6 May 2014 (UTC)

 * There is no fixed limit and the used algorithms don't stop working at some size. They just require more computing power. The difficulty of factoring a number depends not only on the size of the number but also on the form of the number ($$2^{n}-1$$ is easier than most others), and the size and sometimes other properties of its prime factors. And whether a number with a given difficulty is factored depends on how much computer time people are willing to spend on it, and sometimes on whether they get lucky. Integer factorization records says one of the phases for $$2^{1061}-1$$ took about 300 CPU-years. RSA-768 on the same page says "They used the equivalent of almost 2000 years of computing on a single core 2.2 GHz AMD Opteron." Factoring is important in decryption so there is also the possibility that some organizations keep their capabilities secret. NSA has a lot of computing power and we don't know whether they have better algorithms than what is publicy known. PrimeHunter (talk) 23:57, 8 May 2014 (UTC)

But why the 545-bit number (884150927133......083700084281), which is a factor of 10^495-1, can't be factored? — Preceding unsigned comment added by 140.113.136.218 (talk) 04:33, 12 May 2014 (UTC)

 * As I said: "whether a number with a given difficulty is factored depends on how much computer time people are willing to spend on it". Apparently nobody has yet spend the time to factor this. It's non-trivial but certainly can be done. There are many people working on factoring bn±1 for small b including 10, and they will surely get to this number at some time. If you are interested in factoring discussions then check out http://mersenneforum.org/. PrimeHunter (talk) 11:35, 12 May 2014 (UTC)

 * Also, even a tiny amount of research would have shown that the number is mostly factored, with only a 164-digit cofactor. In any case take this discussion elsewhere, the purpose of the Talk pages is to build an encyclopedia not discuss ancillary topics. - CRGreathouse (t | c) 23:33, 14 May 2014 (UTC)

Integer Factoring is to Multiply as Complex Number Factoring is to Plus
Complex Number Factoring is NPComplete

Subset Sum (given n integers, answer does any nonempty subset sum to 0) of n integers can be calculated as multiplying n complex numbers (each of magnitude 1) which are all scaled by the sum of all the integers so it can wrap around less than a half turn either direction in total.

The multiply of 2 complex numbers whose magnitude is 1 adds their angles around complex unit circle. Negative angle is the same as dividing by the positively angled complex number. Angle is normally ambiguous since it repeats on intervals of 2*pi, but since its scaled so it cant wrap around in total, each angle it can reach uniquely represents an integer.

Complex Number Factoring is NPComplete, based on that alone. Here's some more info...

If you multiply all the integers by 2, offset each of them by half their value, and move that value into the target sum of the subset to find, and do the same for the new target sum, then subset sum can be represented as a choice of negative or positive of the same value for each integer translated that way. On complex unit circle, it looks like rotating clockwise vs counterclockwise for each integer thats included or not. To solve Subset Sum you would factor 1.

Its not a root of unity. Its factors of unity limited to a set of possible factors.

It can also be represented as all being positive angled magnitude 1 complex numbers and looking for a Subset Multiply that equals that complex number.

Integer Factoring is to Multiply as Complex Number Factoring is to Plus. — Preceding unsigned comment added by 66.169.5.181 (talk) 19:53, 15 December 2014 (UTC)

 * a) This is wrong.
 * b) It is original research, and therefore not useful for WP.
 * --Macrakis (talk) 23:08, 15 December 2014 (UTC)
 * It's not even wrong. Absent any notion of unique factorization of complex numbers of norm 1 (i.e. on the unit circle) it's meaningless.  The Gaussian integers do form a unique factorization domain but only four of them lie on the unit circle and all Gaussian primes lie strictly outside the unit circle.   Vaughan Pratt (talk) 22:41, 19 March 2016 (UTC)

 * Are you quoting Pauli, Not even wrong? :-) Bubba73 You talkin' to me? 23:46, 19 March 2016 (UTC)
 * Yes, if stealing can be called quoting. ;) Vaughan Pratt (talk) 07:35, 2 May 2016 (UTC)

"It factored the number 15"
Does anyone else laugh when they get to that line? 68.2.235.85 (talk) —Preceding undated comment added 00:27, 6 June 2016 (UTC)

I would argue that factoring 15 did nothing to demonstrate their method. In binary 15 is 1111. The number 15 is 3×5, which in binary is computed 11×101, and is equivalent to writing 101+0101. In factoring 15, their was no untangling of the superposition of bits (or qbits) whatsoever!!!!! The bit pattern 101 just falls straight out of the pattern 1111. The claims made for Shor's algorithm are absurd at best. Runestone1 (talk) 01:09, 8 September 2016 (UTC)

Is RSA cryptosystem broken ?
Look at this presentation. Bosons1978 (talk) 15:32, 11 February 2021 (UTC)
 * This is a self published source, so it cannot be used in Wikipedia per policy WP:NOR. Moreover, I have had a quick look on the link, and it is almost immediately clear that the algorithm cannot be correct. Also, if it were correct and as fast as claimed, this would be cited in many articles, and even in news, which is not the case. D.Lazard (talk) 16:24, 11 February 2021 (UTC)
 * Unlike many other crank-magnet problems (e.g. P vs NP), there's a very very easy way to get taken seriously. Publish the factors of RSA-2048. If anyone does that, we can throw out WP:RS and WP:NOR out the window, per WP:SKYBLUE. I'm not holding my breath here, but has this author done so? Suffusion of Yellow (talk) 20:00, 11 February 2021 (UTC)

If its the same thing, then it is now now published as a paper in the International Association for Cryptologic Research journal by renown mathematician and cryptographer Claus P. Schnorr. HN discussion. Balupton (talk) 01:45, 3 March 2021 (UTC)

 * As it's now published in a journal. I've gone ahead and made an edit to the main page. Balupton (talk) 02:10, 3 March 2021 (UTC)
 * eprint.iacr.org is a preprint server, not a journal. As their homepage says, Papers have been placed here by the authors and did not undergo any refereeing process other than verifying that the work seems to be within the scope of cryptology. XOR'easter (talk) 02:18, 3 March 2021 (UTC)
 * Also, the text abstract and the one in the PDF itself don't match; in particular, the statement "This destroyes [sic] the RSA cryptosystem" was tacked on to the text version, which is iffy. A bit more eyebrow-raising is that the PDF is labeled work in progress 31.10.2019, while the author's website has what appears to be a more recent version, dated 04.03.2020. Something's off. XOR'easter (talk) 05:21, 3 March 2021 (UTC)
 * I agree. It is highly unlikely that the claim is correct, and it fails Wikipedia's verifiability standards. NealKoblitz (talk) 12:04, 5 March 2021 (UTC)

b = 2b proven?
Just kidding, of course. But in the section "Prime decomposition" is the line $b = \sqrt{a^2 - n} = \sqrt{4} = 2b $, which is either (a) missing punctuation or more likely (b) has an extraneous 'b' at the end. Now I've done my share of factoring, but that was 50 yarn ago. Would someone more active kindly make the edit? Thanks, JohnH~enwiki (talk) 20:10, 19 July 2023 (UTC)
 * I have removed the wrong b. PrimeHunter (talk) 22:56, 19 July 2023 (UTC)

title: Talk:Integer factorization


text:
Incompatible-properties argument

The incompatible-properties argument is the idea that no description of God is consistent with reality. For example, if one takes the definition of God to be described fully from the Bible, then the claims of what properties God has described therein might be argued to lead to a contradiction.

Evil vs. good and omnipotence
The problem of evil is the argument that the existence of evil is incompatible with the concept of an omnipotent and perfectly good God.

A variation does not depend on the existence of evil. A truly omnipotent God could create all possible worlds. A "good" God can create only "good" worlds. A God that created all possible worlds would have no moral qualities whatsoever, and could be replaced by a random generator. The standard response is to argue a distinction between "could create" and "would create." In other words, God "could" create all possible worlds but that is simply not in God's nature. This has been argued by theologians for centuries. However, the result is that a "good" God is incompatible with some possible worlds, thus incapable of creating them without losing the property of being a totally different God. Yet, it is not necessary for God to be "good". He simply is good, but is capable of evil.

Purpose vs. timelessness
One argument based on incompatible properties rests on a definition of God that includes a will, plan or purpose and an existence outside of time. To say that a being possesses a purpose implies an inclination or tendency to steer events toward some state that does not yet exist. This, in turn, implies a privileged direction, which we may call "time". It may be one direction of causality, the direction of increasing entropy, or some other emergent property of a world. These are not identical, but one must exist in order to progress toward a goal.

In general, God's time would not be related to our time. God might be able to operate within our time without being constrained to do so. However, God could then step outside this game for any purpose. Thus God's time must be aligned with our time if human activities are relevant to God's purpose. (In a relativistic universe, presumably this means—at any point in spacetime—time measured from t=0 at the Big Bang or end of inflation.)

A God existing outside of any sort of time could not create anything because creation substitutes one thing for another, or for nothing. Creation requires a creator that existed, by definition, prior to the thing created.

Omniscience vs. indeterminacy or free will
Another pair of alleged incompatible properties is omniscience and either indeterminacy or free will. Omniscience concerning the past and present (properly defined relative to Earth) is not a problem, but there is an argument that omniscience regarding the future implies it has been determined, what seems possible only in a deterministic world.

title: Incompatible-properties argument


text:
International Society of Olympic Historians

The International Society of Olympic Historians (ISOH) is a non-profit organization founded in 1991 with the purpose of promoting and studying the Olympic Movement and the Olympic Games. The majority of recent books on the Olympic Games have been written by ISOH members. The ISOH publishes the Journal of Olympic History (JOH, formerly Citius, Altius, Fortius) three times a year.

History
The International Society of Olympic Historians was formed as the result of a meeting in London, England, in December 1991. The idea of forming an Olympic historical society had been the subject of correspondence – mainly between Bill Mallon (United States) and Ture Widlund (Sweden) – for many years. On Thursday, 5 December 1991, a group of potential members met at the Duke of Clarence, a small pub in the Kensington section of London. Those present were Ian Buchanan (Great Britain), Stan Greenberg (Great Britain), Ove Karlsson (Sweden), Bill Mallon (United States), Peter Matthews (Great Britain), David Wallechinsky (United States), and Ture Widlund (Sweden). The invited guests who sent regrets were: Anthony Bijkerk (Netherlands), Peter Diamond (United States), Pim Huurman (Netherlands), Erich Kamper (Austria), Volker Kluge (Germany), John Lucas (United States), and Wolf Lyberg (Sweden).

ISOH was formed with the purpose of promoting and studying the Olympic Movement and the Olympic Games. This purpose is achieved primarily through research into their history, through the gathering of historical and statistical data concerning the Olympic Movement and Olympic Games, through the publication of the research via journals and other publications, and through the cooperation of the membership.

From its inception to 2000, Ian Buchanan has been the president of the ISOH. In 2000, this function was taken over by Bill Mallon. From 2004 to 2012 Dr. Karl Lennartz (Germany) and from 2012 to 2020 David Wallechinsky (United States) served as presidents. Since 2020 the archaeologist and sports historian Dr. Christian Wacker (Germany) has been president.

Journal of Olympic History
The ISOH publishes the Journal of Olympic History (formerly Citius, Altius, Fortius).

Membership
, the ISOH has about 340 members from 48 nations. The membership includes well-known Olympic historians and researchers on Olympic topics. The majority of recent books on the Olympic Games have been written by ISOH members. Over 20 ISOH members have received the Olympic Order for their contributions to the Olympic Movement, and several members of the IOC and several Olympians are members.

Notable members

 * Raleigh DeGeer Amyx, collector of Olympic memorabilia
 * Bob Barney, university professor and founder of the International Center for Olympic Studies