text:
Talk:Kingdom of Kush

Map
User:MilosHaran deleted the current with the simple comment: "Not accurate map." The problem is that there is no accurate map of the Kingdom of Kush, and the map the article had was within the space that even the National Geographic defined it: "Kush was a part of Nubia, loosely described as the region between the Cataracts of the Nile." So, I brought the map back since it shows the region clearly enough. I am open to other interpretations. Caballero / Historiador⎌ 23:15, 7 October 2018 (UTC)

 * I agree with @milosHaran that a map of Africa with a heading 1000 BCE to xxxx should not show Egypt as a part of PersiaEditorfromMars (talk) 22:10, 27 August 2020 (UTC)

A Commons file used on this page or its Wikidata item has been nominated for deletion
The following Wikimedia Commons file used on this page or its Wikidata item has been nominated for deletion: Participate in the deletion discussion at the. —Community Tech bot (talk) 17:39, 4 July 2021 (UTC)
 * A Kushite man.jpg

kushite religion
To Vif12vf, meroitic polythiesm is a synchronization of earlier kerman influences and later egyptian influneces,the dieties like apadamak (and a few others) are of nubian origin not egyptian origin so blanket statements like it all belongs into "ancient egyptian religion is careless and inaccurate. Jedorton (talk) 23:18, 2 October 2022 (UTC)

Reference to "Noba Invasions"
Hi editors There seems to be a mistake in the reference to the end of Meroe. The introductory wording seem to blame a group called the "Noba" as the main instigators of events that eventually led to the destruction of Meroe. Other than a single source written by Mr Riley (who I should point out is a linguist and not an archaeologist) there is no other source that agree with that claim. Historical source and archaeological evidence contradicts this. Also note that even in the cited paper by Mr Riley, it is clear that he was proposing a theory and not a fact. What is known of that period at the end of the 4th century CE is that Ezana, King of Aksum, brought the centralized government in Meroe to an end, however Meroitic culture evolved into what is currently referred to as the Nubian culture. Further more, the introductory body of the article contradicts what is written in the section concerning the end of Kush (Section Roman Period). "Noba" is not an ethnic term and extrapolating the genesis of the modern term Nubian and tying it with the "Noba" is nothing more than speculation. The speaker of the Nubian languages have been present since before the time of Meroe according to Meroitic and Egyptian texts with a different endonym. Nubian culture is the only link we have in the Sudan to the ancient civilizations of the Middle Nile valley, this is established fact. There can be no room for revisionists to rewrite history according to their whims and biases. Finally, dear editors , the Nubians of the Sudan and Egypt are under the pressure of Nationalist Egyptians and revisionist Sudanese who have a political agenda against the indigenous population of the Nile valley. Please do not allow them to use this platform to further their anti Nubian propaganda. We have all the academic data ( not obscure online reference) required on demand that supports the data provided. Kryako (talk) 13:37, 20 December 2023 (UTC)

 * @Kryako I can guarantee the the biases aren't there the Noba threating the axumite borders was as already there mentioned by the axumites further more I we have kushite sources (meroitic sources) that the Nubians were a distinct population. Jedorton (talk) 17:21, 28 February 2024 (UTC)
 * @Jedorton Your guarantees do not change the facts. The proven archeological fact is that the modern nubian, and no one else in the Nile Valley, are the only direct descendants of the ancient population since before Kerma.
 * I do not think you, or anybody, understands Merotic to make such a claim. 88.85.240.34 (talk) 10:56, 25 March 2024 (UTC)
 * Since we are now agreed to be civil, I understand you are requesting an edit. can you please use the format
 * Change this:
 * To this:
 * Why including a reliable source:
 * this will make it easier. Avoid broad accusation, like the Nubians of the Sudan and Egypt are under the pressure of Nationalist Egyptians ... and using weasel words, like saying Historical source and archaeological evidence contradicts this. without giving a source(s) FuzzyMagma (talk) 09:17, 1 April 2024 (UTC)
 * 27 March 2024 (UTC)

Kryako (talk) 09:40, 31 March 2024 (UTC)
 * Can we please take a step back before this leads to both of you being blocked indefinitely for personal attacks?
 * I am glad you came to the page talk and did not engage in edit warring. There are several ways to resolve this amicably. First, let’s please try and get a third opinion using WP:3O page.
 * Can the two of you, state your claim(s) using reliable sources and leave it at that. We have no interest in your credentials or opinion, just information that are written in reliable sources. Once that is done, I (or you) can request a third informed opinion.
 * Until then, please disengage, and go and edit other pages that need your energy. FuzzyMagma (talk) 15:53, 29 March 2024 (UTC)

 * I did and warned them, and asked them to change there approach which they say they will FuzzyMagma (talk) 14:00, 31 March 2024 (UTC)
 * In that case, I accept. Thank you Kryako (talk) 14:01, 31 March 2024 (UTC)
 * Thanks. I will remove my ANI once you edit your comments. Same for you @Jedorton FuzzyMagma (talk) 14:06, 31 March 2024 (UTC)
 * It is done Kryako (talk) 14:10, 31 March 2024 (UTC)
 * @Kryako it’s not. Please read through WP:Personal attacks and amend accordingly. Or just remove the comment entirely and start fresh while focusing on arguing your point rather than the person. FuzzyMagma (talk) 14:15, 31 March 2024 (UTC)
 * If I may, I have been following these pages for a while. This whole thing could have been avoided. But Jedorton started abusing the editor for no reason. Kryaki wrote a nice paragraph on the Noba invasions then Jedorton responded with insults almost instantaneously.
 * Still, you cannot attack an editor. @Jedorton is certainly wrong and they need to amend their comments. They did apologise on talk. I expect @Kryako to do the same. Two wrongs doesn’t make it right FuzzyMagma (talk) 14:02, 31 March 2024 (UTC)

I have no interest in wading into the content dispute here -- however I'm here to tell you all that the behavior on this talk page is absolutely unacceptable. Do not refer to other editors at "butthurt" or "delusional" or "ignoramus" or any of the other insults that I'm seeing on this page. Any further personal attacks from editors here are going to result in immediate blocking without further warning. ⇒  SWAT Jester   Shoot Blues, Tell VileRat! 19:54, 31 March 2024 (UTC)

Why this map
Why does the map lay claim to Egypt, a three thousand year old kingdom who was more often the ruler of Kush, instead of showing the heartlands, core and historically fundament part of Kush? Like having a map of Britain that shows only the peak British Empire. Dustek (talk) 12:50, 7 April 2024 (UTC)

The Kushites and nubians were not the same people
The nubians were not of the same ethnicity as the Kushites, and Nubians spoke a different language, the latter arrived on the scene in later times. Jedorton (talk) 18:08, 27 June 2024 (UTC)

 * Be bold but make sure to use reliable sources FuzzyMagma (talk) 18:31, 27 June 2024 (UTC)
 * @Cookiemonster1618 maybe this was directed at your latest edit. FuzzyMagma (talk) 18:33, 27 June 2024 (UTC)
 * What latest edit? Cookiemonster1618 (talk) 19:15, 27 June 2024 (UTC)

title: Talk:Kingdom of Kush


text:
Relative permittivity

The relative permittivity (in older texts, dielectric constant) is the permittivity of a material expressed as a ratio with the electric permittivity of a vacuum. A dielectric is an insulating material, and the dielectric constant of an insulator measures the ability of the insulator to store electric energy in an electrical field.

Permittivity is a material's property that affects the Coulomb force between two point charges in the material. Relative permittivity is the factor by which the electric field between the charges is decreased relative to vacuum.

Likewise, relative permittivity is the ratio of the capacitance of a capacitor using that material as a dielectric, compared with a similar capacitor that has vacuum as its dielectric. Relative permittivity is also commonly known as the dielectric constant, a term still used but deprecated by standards organizations in engineering as well as in chemistry.

Definition
Relative permittivity is typically denoted as $ε_{r}(ω)$ (sometimes $κ$, lowercase kappa) and is defined as
 * $$\varepsilon_\text{r}(\omega) = \frac{\varepsilon(\omega)}{\varepsilon_{0}},$$

where ε(ω) is the complex frequency-dependent permittivity of the material, and ε0 is the vacuum permittivity.

Relative permittivity is a dimensionless number that is in general complex-valued; its real and imaginary parts are denoted as:
 * $$ \varepsilon_\text{r}(\omega) = \varepsilon_\text{r}'(\omega) - i \varepsilon_\text{r}''(\omega). $$

The relative permittivity of a medium is related to its electric susceptibility, $χ_{e}$, as $ε_{r}(ω) = 1 + χ_{e}$.

In anisotropic media (such as non cubic crystals) the relative permittivity is a second rank tensor.

The relative permittivity of a material for a frequency of zero is known as its static relative permittivity.

Terminology
The historical term for the relative permittivity is dielectric constant. It is still commonly used, but has been deprecated by standards organizations, because of its ambiguity, as some older reports used it for the absolute permittivity ε. The permittivity may be quoted either as a static property or as a frequency-dependent variant, in which case it is also known as the dielectric function. It has also been used to refer to only the real component ε′r of the complex-valued relative permittivity.

Physics
In the causal theory of waves, permittivity is a complex quantity. The imaginary part corresponds to a phase shift of the polarization $P$ relative to $E$ and leads to the attenuation of electromagnetic waves passing through the medium. By definition, the linear relative permittivity of vacuum is equal to 1, that is ε = ε0, although there are theoretical nonlinear quantum effects in vacuum that become non-negligible at high field strengths.

The following table gives some typical values.

The relative low frequency permittivity of ice is ~96 at −10.8 °C, falling to 3.15 at high frequency, which is independent of temperature. It remains in the range 3.12–3.19 for frequencies between about 1 MHz and the far infrared region.

Measurement
The relative static permittivity, εr, can be measured for static electric fields as follows: first the capacitance of a test capacitor, C0, is measured with vacuum between its plates. Then, using the same capacitor and distance between its plates, the capacitance C with a dielectric between the plates is measured. The relative permittivity can be then calculated as
 * $$\varepsilon_\text{r} = \frac{C}{C_0}.$$

For time-variant electromagnetic fields, this quantity becomes frequency-dependent. An indirect technique to calculate εr is conversion of radio frequency S-parameter measurement results. A description of frequently used S-parameter conversions for determination of the frequency-dependent εr of dielectrics can be found in this bibliographic source. Alternatively, resonance based effects may be employed at fixed frequencies.

Energy
The relative permittivity is an essential piece of information when designing capacitors, and in other circumstances where a material might be expected to introduce capacitance into a circuit. If a material with a high relative permittivity is placed in an electric field, the magnitude of that field will be measurably reduced within the volume of the dielectric. This fact is commonly used to increase the capacitance of a particular capacitor design. The layers beneath etched conductors in printed circuit boards (PCBs) also act as dielectrics.

Communication
Dielectrics are used in radio frequency (RF) transmission lines. In a coaxial cable, polyethylene can be used between the center conductor and outside shield. It can also be placed inside waveguides to form filters. Optical fibers are examples of dielectric waveguides. They consist of dielectric materials that are purposely doped with impurities so as to control the precise value of εr within the cross-section. This controls the refractive index of the material and therefore also the optical modes of transmission. However, in these cases it is technically the relative permittivity that matters, as they are not operated in the electrostatic limit.

Environment
The relative permittivity of air changes with temperature, humidity, and barometric pressure. Sensors can be constructed to detect changes in capacitance caused by changes in the relative permittivity. Most of this change is due to effects of temperature and humidity as the barometric pressure is fairly stable. Using the capacitance change, along with the measured temperature, the relative humidity can be obtained using engineering formulas.

Chemistry
The relative static permittivity of a solvent is a relative measure of its chemical polarity. For example, water is very polar, and has a relative static permittivity of 80.10 at 20 °C while n-hexane is non-polar, and has a relative static permittivity of 1.89 at 20 °C. This information is important when designing separation, sample preparation and chromatography techniques in analytical chemistry.

The correlation should, however, be treated with caution. For instance, dichloromethane has a value of εr of 9.08 (20 °C) and is rather poorly soluble in water (13g/L or 9.8mL/L at 20 °C); at the same time, tetrahydrofuran has its εr = 7.52 at 22 °C, but it is completely miscible with water. In the case of tetrahydrofuran, the oxygen atom can act as a hydrogen bond acceptor; whereas dichloromethane cannot form hydrogen bonds with water.

This is even more remarkable when comparing the εr values of acetic acid (6.2528) and that of iodoethane (7.6177). The large numerical value of εr is not surprising in the second case, as the iodine atom is easily polarizable; nevertheless, this does not imply that it is polar, too (electronic polarizability prevails over the orientational one in this case).

Lossy medium
Again, similar as for absolute permittivity, relative permittivity for lossy materials can be formulated as:
 * $$ \varepsilon_\text{r} = \varepsilon_\text{r}' - \frac{i\sigma}{\omega\varepsilon_0}, $$

in terms of a "dielectric conductivity" σ (units S/m, siemens per meter), which "sums over all the dissipative effects of the material; it may represent an actual [electrical] conductivity caused by migrating charge carriers and it may also refer to an energy loss associated with the dispersion of ε′ [the real-valued permittivity]" ( p. 8). Expanding the angular frequency ω = 2πc/λ and the electric constant ε0 = 1/μ0c2, which reduces to:
 * $$ \varepsilon_\text{r} = \varepsilon_\text{r}' - i\sigma\lambda\kappa, $$

where λ is the wavelength, c is the speed of light in vacuum and κ = μ0c/2π = 59.95849 Ω ≈ 60.0 Ω is a newly introduced constant (units ohms, or reciprocal siemens, such that σλκ = εr remains unitless).

Metals
Permittivity is typically associated with dielectric materials, however metals are described as having an effective permittivity, with real relative permittivity equal to one. In the high-frequency region, which extends from radio frequencies to the far infrared and terahertz region, the plasma frequency of the electron gas is much greater than the electromagnetic propagation frequency, so the refractive index n of a metal is very nearly a purely imaginary number. In the low frequency regime, the effective relative permittivity is also almost purely imaginary: It has a very large imaginary value related to the conductivity and a comparatively insignificant real-value.

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

title: Relative permittivity


text:
Lake trout

The lake trout (Salvelinus namaycush) is a freshwater char living mainly in lakes in northern North America. Other names for it include mackinaw, namaycush, lake char (or charr), touladi, togue, and grey trout. In Lake Superior, it can also be variously known as siscowet, paperbelly and lean. The lake trout is prized both as a game fish and as a food fish. Those caught with dark coloration may be called mud hens.

Taxonomy
It is the only member of the subgenus Cristovomer, which is more derived than the subgenus Baione (the most basal clade of Salvelinus, containing the brook trout (S. fontinalis) and silver trout (S. agasizii)) but still basal to the other members of Salvelinus.

Range
From a zoogeographical perspective, lake trout have a relatively narrow distribution. They are native only to the northern parts of North America, principally Canada, but also Alaska and, to some extent, the northeastern United States. Lake trout have been widely introduced into non-native waters in North America and into many other parts of the world, mainly Europe, but also into South America and certain parts of Asia. Although lake trout were introduced into Yellowstone National Park's Shoshone, Lewis and Heart lakes legally in the 1890s, they were illegally or accidentally introduced into Yellowstone Lake in the 1980s where they are now considered invasive.

Description
Lake trout are the largest of the chars; the record weighed almost 102 lb (netted) with a length of 50 in, and 15 - 40 lb fish are not uncommon. The average length is 24 - 36 in. The largest caught on a rod and reel according to the IGFA was 72 lb, caught in Great Bear Lake in 1995 with a length of 59 in.

Life history
Lake trout inhabit cold, oxygen-rich waters. They are pelagic during the period of summer stratification in dimictic lakes, often living at depths of 20 - 60 m.

The lake trout is a slow-growing fish, typical of oligotrophic waters. It is also very late to mature. Populations are extremely susceptible to overfishing. Many native lake trout populations have been severely damaged through the combined effects of hatchery stocking (planting) and over harvest. Another threat to lake trout is acidification, which can have longterm effects on their populations through both direct harm and reduced prey populations (e.g. Mysis relicta).

There are three subspecies of lake trout. There is the common lake trout (Salvelinus namaycush namaycush), the siscowet lake trout (Salvelinus namaycush siscowet), and the less common rush lake trout (Salvelinus namaycush huronicus). Some lakes do not have pelagic forage fish during the period of summer stratification. In these lakes, lake trout act as planktivores. Lake trout in planktivorous populations are highly abundant, grow very slowly and mature at relatively small sizes. In those lakes that do contain deep-water forage, lake trout become piscivorous. Piscivorous lake trout grow much more quickly, mature at a larger size and are less abundant. Notwithstanding differences in abundance, the density of biomass of lake trout is fairly consistent in similar lakes, regardless of whether the lake trout populations they contain are planktivorous or piscivorous.

In Lake Superior, common lake trout (S. n. namaycush) and siscowet lake trout (S. n. siscowet) live together. Common lake trout tend to stay in shallower waters, while siscowet lake trout stay in deeper water. Common lake trout (also called "lean" lake trout) are slimmer than the relatively fat siscowet. Siscowet numbers have become greatly depressed over the years due to a combination of the extirpation of some of the fish's deep water coregonine prey and to overexploitation. Siscowet tend to grow extremely large and fat and attracted great commercial interest in the last century. Their populations have rebounded since 1970, with one estimate putting the number in Lake Superior at 100 million. Professor of Zoology at the University of Wisconsin-Madison James Kitchell credits effective constraint of commercial fisheries and persistent sea lamprey (Petromyzon marinus) control for the successful recovery of Lake Superior's lake trout. "Looking at what has happened in the lake and the results of computer simulations, it is clear that lamprey control needs to continue if Lake Superior is to keep its lake trout."

Hybrids
Lake trout are known to hybridize in nature with the brook trout; such hybrids, known as "splake", are normally sterile but self-sustaining populations exist in some lakes. Splake are also artificially propagated in hatcheries, and then stocked into lakes in an effort to provide sport-fishing opportunities.

Commercial fishing
Lake trout were fished commercially in the Great Lakes until lampreys, overharvest and pollution extirpated or severely reduced the stocks. Commercial fisheries still exist in some areas of the Great Lakes and smaller lakes in northern Canada. Commercial fishing by Ojibwe for Lake Trout in Lake Superior is permitted under various treaties and regulated by the Great Lakes Indian Fish & Wildlife Commission (GLIFWC).

Origin of name
The specific epithet namaycush derives from namekush, a form of the word used in some inland Southern East Cree communities in referring to this species of fish. Other variations found in East Cree are kûkamâs[h], kûkamâw and kûkamesh. Similar cognate words are found in Ojibwe: namegos = "lake trout"; namegoshens = "rainbow trout", literally meaning "little lake trout".

Popular culture
Geneva, New York claims the title "Lake Trout Capital of the World," and holds an annual lake trout fishing derby.

title: Lake trout


text:
Prim's algorithm

In computer science, Prim's algorithm is a greedy algorithm that finds a minimum spanning tree for a weighted undirected graph. This means it finds a subset of the edges that forms a tree that includes every vertex, where the total weight of all the edges in the tree is minimized. The algorithm operates by building this tree one vertex at a time, from an arbitrary starting vertex, at each step adding the cheapest possible connection from the tree to another vertex.

The algorithm was developed in 1930 by Czech mathematician Vojtěch Jarník and later rediscovered and republished by computer scientists Robert C. Prim in 1957 and Edsger W. Dijkstra in 1959. Therefore, it is also sometimes called the Jarník's algorithm, Prim–Jarník algorithm, Prim–Dijkstra algorithm or the DJP algorithm.

Other well-known algorithms for this problem include Kruskal's algorithm and Borůvka's algorithm. These algorithms find the minimum spanning forest in a possibly disconnected graph; in contrast, the most basic form of Prim's algorithm only finds minimum spanning trees in connected graphs. However, running Prim's algorithm separately for each connected component of the graph, it can also be used to find the minimum spanning forest. In terms of their asymptotic time complexity, these three algorithms are equally fast for sparse graphs, but slower than other more sophisticated algorithms. However, for graphs that are sufficiently dense, Prim's algorithm can be made to run in linear time, meeting or improving the time bounds for other algorithms.

Description
The algorithm may informally be described as performing the following steps: 1. Initialize a tree with a single vertex, chosen arbitrarily from the graph.

2. Grow the tree by one edge: Of the edges that connect the tree to vertices not yet in the tree, find the minimum-weight edge, and transfer it to the tree.

3. Repeat step 2 (until all vertices are in the tree).

In more detail, it may be implemented following the pseudocode below. 1. Associate with each vertex v of the graph a number C[v] (the cheapest cost of a connection to v) and an edge E[v] (the edge providing that cheapest connection). To initialize these values, set all values of C[v] to +∞ (or to any number larger than the maximum edge weight) and set each E[v] to a special flag value indicating that there is no edge connecting v to earlier vertices.

2. Initialize an empty forest F and a set Q of vertices that have not yet been included in F (initially, all vertices).

3. Repeat the following steps until Q is empty: 1. Find and remove a vertex v from Q having the minimum possible value of C[v]

2. Add v to F

3. Loop over the edges vw connecting v to other vertices w. For each such edge, if w still belongs to Q and vw has smaller weight than C[w], perform the following steps: 1. Set C[w] to the cost of edge vw

2. Set E[w] to point to edge vw.

4. Return F, which specifically includes the corresponding edges in E

As described above, the starting vertex for the algorithm will be chosen arbitrarily, because the first iteration of the main loop of the algorithm will have a set of vertices in Q that all have equal weights, and the algorithm will automatically start a new tree in F when it completes a spanning tree of each connected component of the input graph. The algorithm may be modified to start with any particular vertex s by setting C[s] to be a number smaller than the other values of C (for instance, zero), and it may be modified to only find a single spanning tree rather than an entire spanning forest (matching more closely the informal description) by stopping whenever it encounters another vertex flagged as having no associated edge.

Different variations of the algorithm differ from each other in how the set Q is implemented: as a simple linked list or array of vertices, or as a more complicated priority queue data structure. This choice leads to differences in the time complexity of the algorithm. In general, a priority queue will be quicker at finding the vertex v with minimum cost, but will entail more expensive updates when the value of C[w] changes.

Time complexity

The time complexity of Prim's algorithm depends on the data structures used for the graph and for ordering the edges by weight, which can be done using a priority queue. The following table shows the typical choices:

A simple implementation of Prim's, using an adjacency matrix or an adjacency list graph representation and linearly searching an array of weights to find the minimum weight edge to add, requires O( | V | 2) running time. However, this running time can be greatly improved by using heaps to implement finding minimum weight edges in the algorithm's inner loop.

A first improved version uses a heap to store all edges of the input graph, ordered by their weight. This leads to an O(|E| log |E|) worst-case running time. But storing vertices instead of edges can improve it still further. The heap should order the vertices by the smallest edge-weight that connects them to any vertex in the partially constructed minimum spanning tree (MST) (or infinity if no such edge exists). Every time a vertex v is chosen and added to the MST, a decrease-key operation is performed on all vertices w outside the partial MST such that v is connected to w, setting the key to the minimum of its previous value and the edge cost of (v,w).

Using a simple binary heap data structure, Prim's algorithm can now be shown to run in time O( | E | log | V | ) where | E | is the number of edges and | V | is the number of vertices. Using a more sophisticated Fibonacci heap, this can be brought down to O( | E | + | V | log | V | ), which is asymptotically faster when the graph is dense enough that | E | is ω( | V | ), and linear time when |E| is at least |V| log |V|. For graphs of even greater density (having at least |V|c edges for some c > 1), Prim's algorithm can be made to run in linear time even more simply, by using a d-ary heap in place of a Fibonacci heap.

Proof of correctness
Let P be a connected, weighted graph. At every iteration of Prim's algorithm, an edge must be found that connects a vertex in a subgraph to a vertex outside the subgraph. Since P is connected, there will always be a path to every vertex. The output Y of Prim's algorithm is a tree, because the edge and vertex added to tree Y are connected. Let Y1 be a minimum spanning tree of graph P. If Y1=Y then Y is a minimum spanning tree. Otherwise, let e be the first edge added during the construction of tree Y that is not in tree Y1, and V be the set of vertices connected by the edges added before edge e. Then one endpoint of edge e is in set V and the other is not. Since tree Y1 is a spanning tree of graph P, there is a path in tree Y1 joining the two endpoints. As one travels along the path, one must encounter an edge f joining a vertex in set V to one that is not in set V. Now, at the iteration when edge e was added to tree Y, edge f could also have been added and it would be added instead of edge e if its weight was less than e, and since edge f was not added, we conclude that

 * $$w(f) \ge w(e).$$

Let tree Y2 be the graph obtained by removing edge f from and adding edge e to tree Y1. It is easy to show that tree Y2 is connected, has the same number of edges as tree Y1, and the total weights of its edges is not larger than that of tree Y1, therefore it is also a minimum spanning tree of graph P and it contains edge e and all the edges added before it during the construction of set V. Repeat the steps above and we will eventually obtain a minimum spanning tree of graph P that is identical to tree Y. This shows Y is a minimum spanning tree. The minimum spanning tree allows for the first subset of the sub-region to be expanded into a smaller subset X, which we assume to be the minimum.

Parallel algorithm

The main loop of Prim's algorithm is inherently sequential and thus not parallelizable. However, the inner loop, which determines the next edge of minimum weight that does not form a cycle, can be parallelized by dividing the vertices and edges between the available processors. The following pseudocode demonstrates this.

1. Assign each processor $P_i$ a set $V_i$ of consecutive vertices of length $\tfrac{

2. V

3. }{

4. P

5. }$.

6. Create C, E, F, and Q as in the sequential algorithm and divide C, E, as well as the graph between all processors such that each processor holds the incoming edges to its set of vertices. Let $C_i$, $E_i$ denote the parts of C, E stored on processor $P_i$.

7. Repeat the following steps until Q is empty: 1. On every processor: find the vertex $v_i$ having the minimum value in $C_i$[$v_i$] (local solution).

2. Min-reduce the local solutions to find the vertex v having the minimum possible value of C[v] (global solution).

3. Broadcast the selected node to every processor.

4. Add v to F and, if E[v] is not the special flag value, also add E[v] to F.

5. On every processor: update $C_i$ and $E_i$ as in the sequential algorithm.

8. Return F

This algorithm can generally be implemented on distributed machines as well as on shared memory machines. The running time is $$O(\tfrac{|V|^2}{|P|}) + O(|V| \log |P|)$$, assuming that the reduce and broadcast operations can be performed in $$O(\log |P|)$$. A variant of Prim's algorithm for shared memory machines, in which Prim's sequential algorithm is being run in parallel, starting from different vertices, has also been explored. It should, however, be noted that more sophisticated algorithms exist to solve the distributed minimum spanning tree problem in a more efficient manner.

title: Prim's algorithm


text:
Brute-force attack

In cryptography, a brute-force attack consists of an attacker submitting many passwords or passphrases with the hope of eventually guessing correctly. The attacker systematically checks all possible passwords and passphrases until the correct one is found. Alternatively, the attacker can attempt to guess the key which is typically created from the password using a key derivation function. This is known as an exhaustive key search. This approach doesn't depend on intellectual tactics; rather, it relies on making several attempts.

A brute-force attack is a cryptanalytic attack that can, in theory, be used to attempt to decrypt any encrypted data (except for data encrypted in an information-theoretically secure manner). Such an attack might be used when it is not possible to take advantage of other weaknesses in an encryption system (if any exist) that would make the task easier.

When password-guessing, this method is very fast when used to check all short passwords, but for longer passwords other methods such as the dictionary attack are used because a brute-force search takes too long. Longer passwords, passphrases and keys have more possible values, making them exponentially more difficult to crack than shorter ones due to diversity of characters.

Brute-force attacks can be made less effective by obfuscating the data to be encoded making it more difficult for an attacker to recognize when the code has been cracked or by making the attacker do more work to test each guess. One of the measures of the strength of an encryption system is how long it would theoretically take an attacker to mount a successful brute-force attack against it.

Brute-force attacks are an application of brute-force search, the general problem-solving technique of enumerating all candidates and checking each one. The word 'hammering' is sometimes used to describe a brute-force attack, with 'anti-hammering' for countermeasures.

Basic concept
Brute-force attacks work by calculating every possible combination that could make up a password and testing it to see if it is the correct password. As the password's length increases, the amount of time, on average, to find the correct password increases exponentially.

Theoretical limits
The resources required for a brute-force attack grow exponentially with increasing key size, not linearly. Although U.S. export regulations historically restricted key lengths to 56-bit symmetric keys (e.g. Data Encryption Standard), these restrictions are no longer in place, so modern symmetric algorithms typically use computationally stronger 128- to 256-bit keys.

There is a physical argument that a 128-bit symmetric key is computationally secure against brute-force attack. The Landauer limit implied by the laws of physics sets a lower limit on the energy required to perform a computation of $kT · ln 2$ per bit erased in a computation, where T is the temperature of the computing device in kelvins, k is the Boltzmann constant, and the natural logarithm of 2 is about 0.693 (0.6931471805599453). No irreversible computing device can use less energy than this, even in principle. Thus, in order to simply flip through the possible values for a 128-bit symmetric key (ignoring doing the actual computing to check it) would, theoretically, require 2128 − 1 bit flips on a conventional processor. If it is assumed that the calculation occurs near room temperature (≈300 K), the Von Neumann-Landauer Limit can be applied to estimate the energy required as ≈1018 joules, which is equivalent to consuming 30 gigawatts of power for one year. This is equal to 30×109 W×365×24×3600 s = 9.46×1017 J or 262.7 TWh (about 0.1% of the yearly world energy production). The full actual computation – checking each key to see if a solution has been found – would consume many times this amount. Furthermore, this is simply the energy requirement for cycling through the key space; the actual time it takes to flip each bit is not considered, which is certainly greater than 0 (see Bremermann's limit).

However, this argument assumes that the register values are changed using conventional set and clear operations, which inevitably generate entropy. It has been shown that computational hardware can be designed not to encounter this theoretical obstruction (see reversible computing), though no such computers are known to have been constructed.

As commercial successors of governmental ASIC solutions have become available, also known as custom hardware attacks, two emerging technologies have proven their capability in the brute-force attack of certain ciphers. One is modern graphics processing unit (GPU) technology, the other is the field-programmable gate array (FPGA) technology. GPUs benefit from their wide availability and price-performance benefit, FPGAs from their energy efficiency per cryptographic operation. Both technologies try to transport the benefits of parallel processing to brute-force attacks. In case of GPUs some hundreds, in the case of FPGA some thousand processing units making them much better suited to cracking passwords than conventional processors. For instance in 2022, 8 Nvidia RTX 4090 GPU were linked together to test password strength by using the software Hashcat with results that showed 200 billion eight-character NTLM password combinations could be cycled through in 48 minutes.

Various publications in the fields of cryptographic analysis have proved the energy efficiency of today's FPGA technology, for example, the COPACOBANA FPGA Cluster computer consumes the same energy as a single PC (600 W), but performs like 2,500 PCs for certain algorithms. A number of firms provide hardware-based FPGA cryptographic analysis solutions from a single FPGA PCI Express card up to dedicated FPGA computers. WPA and WPA2 encryption have successfully been brute-force attacked by reducing the workload by a factor of 50 in comparison to conventional CPUs and some hundred in case of FPGAs.

Advanced Encryption Standard (AES) permits the use of 256-bit keys. Breaking a symmetric 256-bit key by brute force requires 2128 times more computational power than a 128-bit key. One of the fastest supercomputers in 2019 has a speed of 100 petaFLOPS which could theoretically check 100 trillion (1014) AES keys per second (assuming 1000 operations per check), but would still require 3.67×1055 years to exhaust the 256-bit key space.

An underlying assumption of a brute-force attack is that the complete key space was used to generate keys, something that relies on an effective random number generator, and that there are no defects in the algorithm or its implementation. For example, a number of systems that were originally thought to be impossible to crack by brute force have nevertheless been cracked because the key space to search through was found to be much smaller than originally thought, because of a lack of entropy in their pseudorandom number generators. These include Netscape's implementation of Secure Sockets Layer (SSL) (cracked by Ian Goldberg and David Wagner in 1995) and a Debian/Ubuntu edition of OpenSSL discovered in 2008 to be flawed. A similar lack of implemented entropy led to the breaking of Enigma's code.

Credential recycling
Credential recycling is the hacking practice of re-using username and password combinations gathered in previous brute-force attacks. A special form of credential recycling is pass the hash, where unsalted hashed credentials are stolen and re-used without first being brute forced.

Unbreakable codes
Certain types of encryption, by their mathematical properties, cannot be defeated by brute force. An example of this is one-time pad cryptography, where every cleartext bit has a corresponding key from a truly random sequence of key bits. A 140 character one-time-pad-encoded string subjected to a brute-force attack would eventually reveal every 140 character string possible, including the correct answer – but of all the answers given, there would be no way of knowing which was the correct one. Defeating such a system, as was done by the Venona project, generally relies not on pure cryptography, but upon mistakes in its implementation, such as the key pads not being truly random, intercepted keypads, or operators making mistakes.

Countermeasures
In case of an offline attack where the attacker has gained access to the encrypted material, one can try key combinations without the risk of discovery or interference. In case of online attacks, database and directory administrators can deploy countermeasures such as limiting the number of attempts that a password can be tried, introducing time delays between successive attempts, increasing the answer's complexity (e.g., requiring a CAPTCHA answer or employing multi-factor authentication), and/or locking accounts out after unsuccessful login attempts. Website administrators may prevent a particular IP address from trying more than a predetermined number of password attempts against any account on the site. Additionally, the MITRE D3FEND framework provides structured recommendations for defending against brute-force attacks by implementing strategies such as network traffic filtering, deploying decoy credentials, and invalidating authentication caches.

Reverse brute-force attack
In a reverse brute-force attack, a single (usually common) password is tested against multiple usernames or encrypted files. The process may be repeated for a select few passwords. In such a strategy, the attacker is not targeting a specific user.

title: Brute-force attack


text:
Dictionary attack

In cryptanalysis and computer security, a dictionary attack is an attack using a restricted subset of a keyspace to defeat a cipher or authentication mechanism by trying to determine its decryption key or passphrase, sometimes trying thousands or millions of likely possibilities often obtained from lists of past security breaches.

Technique
A dictionary attack is based on trying all the strings in a pre-arranged listing. Such attacks originally used words found in a dictionary (hence the phrase dictionary attack); however, now there are much larger lists available on the open Internet containing hundreds of millions of passwords recovered from past data breaches. There is also cracking software that can use such lists and produce common variations, such as substituting numbers for similar-looking letters. A dictionary attack tries only those possibilities which are deemed most likely to succeed. Dictionary attacks often succeed because many people have a tendency to choose short passwords that are ordinary words or common passwords; or variants obtained, for example, by appending a digit or punctuation character. Dictionary attacks are often successful, since many commonly used password creation techniques are covered by the available lists, combined with cracking software pattern generation. A safer approach is to randomly generate a long password (15 letters or more) or a multiword passphrase, using a password manager program or manually typing a password.

Pre-computed dictionary attack/Rainbow table attack
It is possible to achieve a time–space tradeoff by pre-computing a list of hashes of dictionary words and storing these in a database using the hash as the key. This requires a considerable amount of preparation time, but this allows the actual attack to be executed faster. The storage requirements for the pre-computed tables were once a major cost, but now they are less of an issue because of the low cost of disk storage. Pre-computed dictionary attacks are particularly effective when a large number of passwords are to be cracked. The pre-computed dictionary needs be generated only once, and when it is completed, password hashes can be looked up almost instantly at any time to find the corresponding password. A more refined approach involves the use of rainbow tables, which reduce storage requirements at the cost of slightly longer lookup-times. See LM hash for an example of an authentication system compromised by such an attack.

Pre-computed dictionary attacks, or "rainbow table attacks", can be thwarted by the use of salt, a technique that forces the hash dictionary to be recomputed for each password sought, making precomputation infeasible, provided that the number of possible salt values is large enough.

Dictionary attack software

 * Cain and Abel
 * Crack
 * Aircrack-ng
 * John the Ripper
 * L0phtCrack
 * Metasploit Project
 * Ophcrack
 * Cryptool

title: Dictionary attack